0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ could you please show how! pretty lease with sugar on it. or some link $\endgroup$ – Dragon Surfer Mar 10 '16 at 7:37
  • $\begingroup$ thnx. I will try anyways $\endgroup$ – Dragon Surfer Mar 10 '16 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.