# Programming a recursive formula into Mathematica and find the nth position in the sequence

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$$.

\[Alpha] =2;
\[Beta] =1;
\[Gamma] =2;
n =5;

• RSolveValue does exactly this. – Roman Aug 17 '19 at 12:55
• I entered 'recurrence' in the help browser and got several useful hits. So I'd say this comes down to checking documentation. – Daniel Lichtblau Aug 18 '19 at 15:30

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

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


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}}$$

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


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))