Question

(2) Homogeneous Linear Recurrences where p(A) has repeated roots (a) Let Let f(n) = an. Show f(n) = d,2n +d2n2" satisfies a(ai)iez be a sequence of real numbers p(A)f(n) (A 2)2(f(n)) 0 for every di, d2 0. .

no coding solve it by hand

Answer 1

$(A-2)^2(f(n))=(A^2-4A+4)(f(n))=0$

Which means $A^2(f(n))-4A(f(n))+4f(n)=0$

That is, $f(n+2)-4f(n+1)+4f(n)=0$ is what we want to show

Note that $f(n)=d_12^n+d_2n2^n$ means $f(n+1)=d_12^{n+1}+d_2(n+1)2^{n+1}$ and $f(n+2)=d_12^{n+2}+d_2(n+2)2^{n+2}$

So that

$\newline f(n+2)-4f(n+1)+4f(n)=\newline \left(d_12^{n+2}+d_2(n+2)2^{n+2} \right )-4\left(d_12^{n+1}+d_2(n+1)2^{n+1} \right )+4\left(d_12^{n}+d_2n2^{n} \right )$

$\newline f(n+2)-4f(n+1)+4f(n)=d_1\left(2^{n+2}-4\cdot 2^{n+1}+4\cdot 2^n \right )+d_2\left((n+2)2^{n+2}-4\cdot (n+1)2^{n+1}+4\cdot n2^n \right )$

Which equals $\newline f(n+2)-4f(n+1)+4f(n)=d_1\left(2^{n+2}-2^{n+3}+ 2^{n+2} \right )+d_2\left((n+2)2^{n+2}- (n+1)2^{n+3}+ n2^{n+2} \right )$

That is, $\newline f(n+2)-4f(n+1)+4f(n)=d_1\left(2\cdot 2^{n+2}-2^{n+3} \right )+d_2\left((n+2)2\cdot 2^{n+2}- (n+1)2^{n+3}\right )$

Which is $\newline f(n+2)-4f(n+1)+4f(n)=d_1\left(2^{n+3}-2^{n+3} \right )+d_2\left((n+2) 2^{n+3}- (n+1)2^{n+3}\right )$

Cancelling these terms, we get

$\newline f(n+2)-4f(n+1)+4f(n)=d_1\left(0\right )+d_2\left(0\right )$

That is, $\newline f(n+2)-4f(n+1)+4f(n)=0$ as required

Thus, $f(n)=d_12^n+d_2n2^n$ satisfies $(A-2)^2(f(n))=(A^2-4A+4)(f(n))=0$ for every $d_1,d_2\neq 0$

$\blacksquare$

Please do rate this answer positively if you found it helpful. Thanks and have a good day!