TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 16

Man zeige mittels vollständiger Induktion, dass für die rekursiv definierte Folge $x_{0}=1$ und $x_{k+1}=ax_{k}+b$ für $k\geq0$ (wobei $a,b \in \mathbb{R},a\neq1$) allgemein gilt:

$x_{n}=a^{n}+b*\frac{a^{n}-1}{a-1}$, für alle $n\geq0$.

Lösungsvorschlag von Az0r

--Az0r 11:17, 24. Mär. 2019 (CET)

Induktionsanfang:

Wir sehen uns das 2-te Glied der Folge an, wobei der Startwert (erstes Glied) $x_{0}=1$ aus der Angabe vorgegeben ist.

$\begin{align} n&:=1\\ x_{0}&:=1\\ x_{k+1}&=ax_{k}+b\\ x_{n}&=a^{n}+b*\frac{a^{n}-1}{a-1}\\ \end{align}$

Somit:

$\begin{align} A(n):x_{n}=a*x_{n-1}+b&=a^{n}+b*\frac{a^{n}-1}{a-1}\\ A(1):x_{1}=a*x_{1-1}+b&=a^{1}+b*\frac{a^{1}-1}{a-1}\\ A(1):x_{1}=a*x_{0}+b&=a^{1}+b*\frac{a^{1}-1}{a-1}\\ a*1+b & = a+b*\frac{a-1}{a-1}\\ a+b & = a+b\\ \end{align}$

Induktionsannahme:

$\forall n\in\mathbb{N},\forall (a,b,x)\in\mathbb{R},a\neq 1,x\geq 0 |A(n):x_{n}=a^{n}+b*\frac{a^{n}-1}{a-1}$

Induktionsbehauptung:

$A(n+1):x_{0+n+1}=a^{n+1}+b*\frac{a^{n+1}-1}{a-1}$

Induktionsschluss:

$\begin{align} A(n+1):x_{n+1}=a*x_{n}+b&=a^{n+1}+b*\frac{a^{n+1}-1}{a-1}\\ x_{n}&=a^{n}+b*\frac{a^{n}-1}{a-1}\\ \end{align}$

Somit:

$\begin{align} A(n+1):x_{n+1}=a*(a^{n}+b*\frac{a^{n}-1}{a-1})+b&=a^{n+1}+b*\frac{a^{n+1}-1}{a-1}\\ (a^{n+1}+a*b*\frac{a^{n}-1}{a-1})+b&=a^{n+1}+b*\frac{a^{n+1}-1}{a-1}\\ a^{n+1}+\frac{a*b*(a^{n}-1)+b*(a-1)}{a-1}&=a^{n+1}+b*\frac{a^{n+1}-1}{a-1}\\ a^{n+1}+b*\frac{a*(a^{n}-1)+(a-1)}{a-1}&=a^{n+1}+b*\frac{a^{n+1}-1}{a-1}\\ a^{n+1}+b*\frac{a^{n+1}-a+a-1}{a-1}&=a^{n+1}+b*\frac{a^{n+1}-1}{a-1}\\ a^{n+1}+b*\frac{a^{n+1}-1}{a-1}&=a^{n+1}+b*\frac{a^{n+1}-1}{a-1}\\ \end{align}$

$\square$.

Az0r 12:23, 24. Mär. 2019 (CET)