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\geq 0$ (wobei $a,b\in \mathbb {R} ,a\neq 1$) allgemein gilt:

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

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{aligned}n&:=1\\x_{0}&:=1\\x_{k+1}&=ax_{k}+b\\x_{n}&=a^{n}+b*{\frac {a^{n}-1}{a-1}}\\\end{aligned}}$

Somit:

${\begin{aligned}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{aligned}}$

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{aligned}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{aligned}}$

Somit:

${\begin{aligned}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{aligned}}$

$\square$.

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