Mathematisches Beweisen (Induktion...)

Question

Aufgabe:

Text erkannt:

Exercise 1
Recall that the 'Big Sigma' notation for indexed sums \( \sum \limits_{i=k}^{l} x_{i} \) means \( x_{k}+x_{k+1}+\ldots+x_{l} \). Consider the sequence of numbers defined by the recurrence
\( a_{0}=1 \quad \text { and } \quad a_{n}=1+\sum \limits_{i=0}^{n-1} a_{i} \quad \text { for } n \geq 1 \)
a) Prove the auxiliary fact that \( \left(\sum \limits_{i=0}^{k} 2^{i}\right)=2^{0}+2^{1}+\ldots+2^{k}=2^{k+1}-1 \).
b) Prove that \( a_{n}=2^{n} \) by strong induction on \( n \).
c) Can you find an alternative proof of b) that only requires 'normal' mathematical induction?
Hint: Try to manipulate the recurrence for \( a_{n} \) into another, simpler recurrence.

Problem/Ansatz:

also bei der a hab ich leider nichtmal einen Ansatz wie ich das Beweisen soll...

bei b hätte ich es mal so gemacht Induction Hypothesisi: an = 2^n

Induction step: an+1 = 2^n+1

und wegen strong induction dann ak = 2^k und k < n

was meine Schlussfolgerung aus dem is weiß ich leider auch nicht, hab hier nur hoffentlich richtig diese Induction Regeln angewandt...

hoffe mir kann hier wer weiterhelfen

Answer 1

a)  Es gilt für k=1.

 Also angenommen es gibt ein k mit

 #    \( \left(\sum \limits_{i=0}^{k} 2^{i}\right)=2^{0}+2^{1}+\ldots+2^{k}=2^{k+1}-1 \)

Dann folgt für k+1

\( \sum \limits_{i=0}^{k+1} 2^{i}=  \left(\sum \limits_{i=0}^{k} 2^{i}\right) +2^{k+1} \)

wegen # ist das \( =  \left( 2^{k+1} - 1 \right) +2^{k+1} \)

                    \( =  2 \cdot 2^{k+1} - 1  \)

                    \( = 2^{k+2} - 1  \)

Also gilt # auch für k+1 und damit per vollst. Induktion

für alle k∈ℕ.