Sei a eine Folge, die folgendermaßen rekursiv definiert ist:

Sei a eine Folge, die folgendermaßen rekursiv definiert ist:

a₁ = 2

a_n+1 = 2 −  1/a_n 

Zeigen Sie mittels vollst. Induktion: an = (n+1)/ n .

$\begin{array}{|rcll|} \hline a_{n+1}:= 2 - \frac{1}{a_n}\qquad a_1 = 2 \qquad \text{ Vermutung } a_n = \frac{n+1}{n} \quad n \in N \\ \hline \end{array}$

Induktionsanfang:

$\begin{array}{|rcll|} \hline n=1 \qquad a_1 = \frac{1+1}{1} = 2~ \checkmark \\ \hline \end{array}$

Induktionsvoraussetzung:

$\begin{array}{|rcll|} \hline a_n = \frac{n+1}{n} \quad n \in N \\ \hline \end{array}$

Induktionsschritt: $n\rightarrow n+1$

$\begin{array}{|rcll|} \hline a_{n+1}= 2 - \frac{1}{a_n} &\overset{IV}{=}& 2-\frac{1}{\frac{n+1}{n}} \\ &=& 2-\frac{n}{n+1} \\ &=& \frac{2\cdot (n+1)-n}{n+1} \\ &=& \frac{(n+1)+(n+1)-n}{(n+1)} \\ &=& \frac{(n+1)+1}{(n+1)} \\ \hline \end{array}$

$\begin{array}{|rcll|} \hline a_n = \frac{n+1}{n} \text { oder }\\ a_{n+1} = \frac{(n+1)+1}{(n+1)}\\ \hline \end{array}$