4
$\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
    $\begingroup$ RSolveValue does exactly this. $\endgroup$ – Roman Aug 17 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$ – Daniel Lichtblau Aug 18 at 15:30
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, privacy policy and cookie policy

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