Programming a recursive formula into Mathematica and find the nth position in the sequencerteMcK I
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;
-
1$\\begingroup$ RSolveValue does exactly this. $\\endgroup$ – Roman 14 hours ago
4 Answers
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
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 *)
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))
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