Solving/Proving Recurrence Relations

Question

Given $a_{k-1}=7*5^{k-1}-3*8^{k-1}$ and

$a_k=7*5^k-3*8^k$

for the recurrence $a_n=13a_{n-1}-40a_{n-2}$ prove that the next term is $a_{k+1}=7*5^{k+1}-3*8^{k+1}$

I am kind of stuck right now. This is what I have so far. If anyone could give me advice on where I should go from here. Thanks

$a_{k+1}=13(7*5^k-3*8^k)-40(7*5^{k-1}-3*8^{k-1})$

$=13*7*5^k-13*3*8^k-40*7*5^{k-1}+40*3*8^{k-1}$

$=7(13*5^k-40*5^{k-1})+3(-13*8^k+40*8^{k-1})$

$=7(13*5-40)*5^{k-1}+3(-13*8+40)*8^{k-1}$

Answer 1

If $a_k =cu^k+dv^k$ then

$\begin{array}\\ ra_{n}+sa_{n-1} &=r(cu^n+dv^n)+s(cu^{n-1}+dv^{n-1})\\ &=c(ru+s)u^{n-1}+d(rv+s)v^{n-1}\\ \end{array} $

and this equals $a_{n+1}$ if $cu^{n+1}+dv^{n+1} =c(ru+s)u^{n-1}+d(rv+s)v^{n-1}$ or $ru+s = u^2$ and $rv+s = v^2$.

In this problem, given $c, d, u, v$, we want to find $r, s$.

Subtracting, $r(u-v) = u+2-v^2$ so $r = u+v$ and $s = u^2-ru =u^2-(u+v)u =-uv $.

Since $a_k=7*5^k-3*8^k $, we have $c=7, d=-3, u=5, v=8$ so $r=13, s=-40$.

Note that $c$ and $d$ do not seem to appear in the formulas for $r$ and $s$. They are determined by the initial values $a_0$ and $a_1$. These are $a_0 = c+d$ and $a_1 =cu+dv$

Answer 2

This is not the easiest way to answer the specific question you have, but it outlines what is going on.

Note that $(x-5)(x-8)=x^2-13x+40$

Now generally, if $p(x)=(x-a)(x-b)=0=x^2-(a+b)x+ab=x^2-px+q$ where $p=a+b$ and $q=ab$ we have $p(a)=0$ and $p(b)=0$ so that $$Aa^{k-1}p(a)+Bb^{k-1}p(b)=0$$

Expanding we find $$(Aa^{k+1}+Bb^{k+1})-p(Aa^k+Bb^k)+q(Aa^{k-1}+Bb^{k-1})=0$$So that if $u_k=Aa^k+Bb^k$ we have $$u_{k+1}=pu_k-qu_{k-1}$$

So there is an intimate relationship between the roots of the quadratic equation and the solutions of the recurrence. You could work it out in general, where the specifics of the arithmetic don't conceal what is going on. With specific numbers involved people tend to compute products and sums, but if you write $13=5+8$ and $40=5\times 8$ you will find it easier to spot both factors and cancellations.

Answer 3

Express $a_{k+1}$ as a linear combination of $5^{k-1}$ and $3^{k-1}$, rework the coefficients and extract the powers of $5$ and $3$.

$$13\,(7\cdot5^k-3\cdot8^k)-40\,(7\cdot5^{k-1}-3\cdot8^{k-1}) \\=(13\cdot7\cdot5-40\cdot7)\,5^{k-1}-(13\cdot3\cdot8-40\cdot3)\,3^{k-1} \\=175\cdot5^{k-1}-192\cdot 3^{k-1} \\=7\cdot5^2\cdot5^{k-1}-3\cdot3^2\cdot8^{k-1} \\=7\cdot5^{k+1}-3\cdot8^{k+1}$$