5
$\begingroup$

Well, I have the following recursive formula (where $\text{n}$ gives the position in the sequence):

$$\text{P}_\text{n}=\alpha\cdot\text{P}_{\text{n}-1}+\text{P}_{\text{n}-2}\tag1$$

For arbitrary $\alpha\in\mathbb{N}^+$.

And I know that $\text{P}_1=\beta$ and $\text{P}_2=\gamma$, where $\beta\space\wedge\space\gamma\in\mathbb{N}^+$.

How can I write a program that gives me the value of the nth position in the sequence?


Example, find the value of the 5th position in the sequence when we know that $\beta=1$ and $\alpha=\gamma=2$. Now it has to give the value $\text{P}_5=29$.

So, I think that the code has to start with:

\[Alpha] =2;
\[Beta] =1;
\[Gamma] =2;
n =5;
$\endgroup$
2
  • 2
    $\begingroup$ RSolveValue does exactly this. $\endgroup$
    – Roman
    Commented Aug 17, 2019 at 12:55
  • $\begingroup$ I entered 'recurrence' in the help browser and got several useful hits. So I'd say this comes down to checking documentation. $\endgroup$ Commented Aug 18, 2019 at 15:30

4 Answers 4

5
$\begingroup$

Try RSolve:

ClearAll[rs]
rs[α_, β_, γ_] := p /. 
  RSolve[{p[n] == α p[n - 1] + p[n - 2], p[1] == β, p[2] == γ}, p, n][[1]]

N @ rs[2, 1, 2][5]

29.

Alternatively, RecurrenceTable:

ClearAll[rt]
rt[α_, β_, γ_][k_] := Last @ 
   RecurrenceTable[{p[n] == α p[n - 1] + p[n - 2], p[1] == β, p[2] == γ}, p,  {n, k}];

rt[2, 1, 2][5]

29

$\endgroup$
5
$\begingroup$

Since you have a three-term linear difference equation, it is very straightforward to use LinearRecurrence[] directly:

With[{α = 2, β = 1, γ = 2}, 
     LinearRecurrence[{α, 1}, {β, γ}, {5}][[1]]]
   29

A more manual, but equivalent, method involves repeatedly multiplying the (Frobenius) companion matrix of your difference equation's characteristic polynomial with a vector containing your initial conditions. MatrixPower[]'s three-argument action form (which directly generates $\mathbf A^n\mathbf v$ as opposed to separately generating $\mathbf A^n$ before multiplying with $\mathbf v$) is particularly convenient for this:

With[{α = 2, β = 1, γ = 2},
     MatrixPower[{{α, 1}, {1, 0}}, 5 - 2, {γ, β}][[1]]]
   29
$\endgroup$
4
$\begingroup$

RSolveValue gives an explicit expression:

RSolveValue[{P[n] == α P[n - 1] + P[n - 2], P[1] == β, P[2] == γ}, P[n], n] // FullSimplify

$$ \frac{2^{-n-1} \left(\left(\alpha -\sqrt{\alpha ^2+4}\right)^n \left(\alpha \gamma -\left(\alpha ^2+2\right) \beta \right)+\left(\sqrt{\alpha ^2+4}+\alpha \right)^n \left(\left(\alpha ^2+2\right) \beta -\alpha \gamma \right)-\alpha \sqrt{\alpha ^2+4} \beta \left(\alpha -\sqrt{\alpha ^2+4}\right)^n-\alpha \sqrt{\alpha ^2+4} \beta \left(\sqrt{\alpha ^2+4}+\alpha \right)^n+\sqrt{\alpha ^2+4} \gamma \left(\alpha -\sqrt{\alpha ^2+4}\right)^n+\sqrt{\alpha ^2+4} \gamma \left(\sqrt{\alpha ^2+4}+\alpha \right)^n\right)}{\sqrt{\alpha ^2+4}} $$

For your particular parameters:

With[{α = 2, β = 1, γ = 2},
  RSolveValue[{P[n] == α P[n - 1] + P[n - 2], P[1] == β, P[2] == γ}, P[5], n]]
(*    29    *)
$\endgroup$
4
$\begingroup$

You can also write this almost verbatim as you stated it:

Clear[p]; p[n_] := p[n] = \[Alpha] p[n - 1] + p[n - 2];
p[1] = 1; p[2] = 2; \[Alpha] = 2;

To get the 5th term:

p[5]
29

Or leave the values unspecified to get the general form:

Clear[p]; p[n_] := p[n] = a p[n - 1] + p[n - 2]; p[1] = b; p[2] = g;

p[5]
b + a g + a (g + a (b + a g))
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.