reccurence relation

Question

Suppose that aⁿ and bⁿ are both solutions to a recurrence relation of the form x_n = αx_n-1 + βx_n-2. Prove that for any constants c and d, c aⁿ + d bⁿ is also a solution to the same recurrence relation.

Answer 1

Hi, Lemur:

Please see below if it helps.

we only need to prove the following

c*a_n + d*b_n = a*( c*a_{n-1}+ d*b_{n-1} ) + b*( c*a_{n-2}+ d*b_{n-2}).

This is actually true since

1) for any c

c*a_n = c*a*a_{n-1}+ c*b*a_{n-2}.

2) for any d

d*b_n = d*a*b_{n-1}+ d*b*b_{n-2}.

Adding both sides together yields the desired results.