Proof for the solution of homogenous difference equation Suppose the output $y_h[n]$ of a linear, time-invariant system is described by by the following equation for input $x[n]=0$,

$$\sum_{k=0}^{N}a_k y_h[n-k] = 0$$

My book states the $y_h[n]$ is in fact a member of a family of solution of the form:

$$y_h[n]=\sum_{m=1}^{N}A_mz_m^n$$

where the complex numbers $z$ are the zeros of $A(z)=\sum_{k=0}^Na_kz^{-k}$.



What is the proof that $y_h$ is in fact of the form given?

A simple substitution would result in:

$$\sum_{k=0}^N (a_k \sum_{m=1}^NA_mz_m^n) = 0$$

but I don't see to proof showing a set $\{z_1,z_2,...,z_N\}$ and $\{A_1, A_2,..., A_N\}$ indeed exist for all n. Sorry if this seems like a poor question.
If you substitute your second equation back into the first equation, you obtain

$$\begin{align}\sum_{k=0}^{N}a_k\sum_{m=1}^NA_mz_m^{n-k}&amp;=\sum_{m=1}^NA_mz_m^n\sum_{k=0}^Na_kz_m^{-k}\end{align}\tag{1}$$

If $z_m$ are zeros of the polynomial

$$A(z)=\sum_{k=0}^Na_kz^{-k}\tag{2}$$

then Eq. $(1)$ equals zero, as required for the homogenous solution.