0

I know for a recurrence relation $$X(n)=c_1X(n-1)+c_2X(n-2).....+c_kX(n-k)$$ the characteristic equation is $$X^n=c_1X^{n-1}+c_2X^{n-2}+...$$ I know the general solution if all roots are equal is $$x(n)=C_1m_1x^n-1+C_2m_2x^{n-2}.....C_km_kx^{n-k}$$

I have no I idea how this general solution came from. can someone give the derivation for the above general solution and for the cases where roots are equal, unique, and mix of equal and unique.

I couldn't find much on the net. I read this book too but its doesn't have the derivation to the above general solution. This general solution is there in many discrete structure books, but no one has written the derivation to this.

Vlad
  • 6,710
Dragon Surfer
  • 179

1 Answers1

0

It's possible to find that using generating functions. First, you define $A(x)=\sum_n a_nx^n$ where $a_n$ are the coefficients you're looking for. Then, by considering $A(x)-c_1A(x)x-c_2A(x)x² \ldots - c_kA(x)x^k$ you can use the recurrence relation to cancel the terms of degree higher than $k$ and ending up with $A(x)=\frac{P(x)}{Q(x)}$ for some polynomials $P$ and $Q$. Then you can find an explicit formula for $a_k$ using Taylor expansion.

Note that we're not talking about the convergence of $A(x)$ since we're just considering formal series and we will not enter any value in the power aerie $A$

H. Potter
  • 2,161