Geschlossenen Ausdruck für rekursiv definiert Folge finden und Korrektheit mit vollständiger Induktion beweisen

Question

Text erkannt:

Ein Standbetreiber des Weihnachtsmarktes möchte die Anzahl der Kunden \( a_{n} \) für jeden Tag \( n \in \mathbb{N}_{>0} \) nach Eröffnung des Marktes abschätzen. Da zufriedene Kunden für gewöhnlich andere Kunden von der Qualität der Produkte überzeugen, hängt \( a_{n} \) unter anderem von der Anzahl der Kunden der vorherigen Tage ab. Es werden verschiedene Annahmen getroffen:
a) Angenommen, es gelte \( a_{n+1}=2 a_{n}+1 \) für alle \( n \geq 1 \), sowie \( a_{1}=7 \).
b) Angenommen, es gelte \( a_{n+2}=a_{n}+4 \) für alle \( n \geq 1 \), sowie \( a_{1}=3, a_{2}=5 \).
c) Angenommen, es gelte \( a_{n}=\left(a_{n-1}\right)^{2} \) für alle \( n \geq 2 \), sowie \( a_{1}=2 \).

Geben Sie jeweils einen geschlossenen, nicht-rekursiven Ausdruck für \( a_{n} \) an und beweisen Sie seine Korrektheit per vollständiger Induktion.

Aufgabe:

Problem/Ansatz:

Guten Abend zusammen. Brauche Unterstützung bei dieser Aufgabe.

Bin schon auf geschlossene, nicht-rekursive Ausdrücke gekommen:
a) A(n) = 7 * 2^(n-1) + 2^(n-1) - 1
b) A(n) = 1 + 2n

c) A(n) = 2ⁿ

Habe gerade Probleme mit dem Korrektheitsbeweis per vollständiger Induktion. bei a) und b) verwirrt mich, dass es um a_n+1 und a_n+2 geht und, dass es bei b) zwei Basisfälle gibt. Bin für eure Hilfe sehr dankbar.

Answer 1

a) A(n) = 7 * 2^(n-1) + 2^(n-1) - 1= 8*2^n-1 - 1 = 2³ * 2^n-1 - 1= 2ⁿ⁺¹ - 1

Vielleicht klappt es damit besser .

Bei b) klappen doch beide Basisfälle mit deiner Formel.

Dann könnte die Induktion doch so laufen.

Angenommen n>2 und die Formel gilt für alle k kleiner als n.

Dann ist zu zeigen: Sie gilt für n und für n+1.

Also zu zeigen A(n)=1+2n . Wegen der Rekursion

hast du A(n)=A(n-2)+4 = 1+2(n-2)+4 = 2n+1 passt also.

Ebenso A(n+1) = A(n-1)+4 = 1+2(n-1)+4 = 2n+5 =1+ 2(n+1) passt auch.

Comments

Danke für deinen Support!

Answer 2

Deine Formeln für a) und b) sind korrekt und mit Induktion beweisbar. Notiere sauber Ind.Anf., Ind.Ann., Ind.Beh..

Bei b) braucht man zwei Ind.Anf., eben für n=1 und n=2. Die benötigte Ind.Ann. lautet: "Gelte für ein \(n : ~~~a_k=1+2k\) für alle \(k\le n\)." Das ist die Version, wenn der Ind.Schritt von \(n\) auf \(n+1\) sein soll.

Bei c) stimmt Deine Formel nicht. Probiere ein paar Werte aus.

Wenn Du den Ind.Schritt nicht von \(n-1\) auf \(n\) machen willst, sondern von \(n\) auf \(n+1\), dann schreib Deine Formeln um in der Form \(a_{n+1}=...\).

Comments

Danke für deinen Support!