Exercise 4.4.1 (Linear recurrence)

Proof. The characteristic polynomial associated to this sequence is

whose unique root is $\lambda =1$. By Theorem 4.1.1, there exist some real constants $\alpha ,\beta$ such that for all $n\in \mathbb{N}$,

• If $u_0=0,u_1=1$, then $\alpha ,\beta$ satisfy the system

  $$\{\begin{array}{cc}\alpha \hfill & =0,\hfill \\ \alpha +\beta \hfill & =1.\hfill \end{array}$$

  Therefore $\alpha =0,\beta =1$, and for all $n\in \mathbb{N}$,

  $$u_n=n.$$

• If $u_0=u_1=1$, then

  $$\{\begin{array}{cc}\alpha \hfill & =1,\hfill \\ \alpha +\beta \hfill & =1.\hfill \end{array}$$

  Therefore $\alpha =1,\beta =0$, and for all $n\in \mathbb{N}$,

  $$u_n=1.$$