Induktionsbeweis zu Folgen

Question

Aufgabe (Folgen):

Es sei \( \lambda: \mathbb{N} \rightarrow \mathbb{N} \) definiert durch:

$$ \lambda(n):=\left\{\begin{array}{ll} 2 & \text { falls } n=0 \\ \lambda(n-1)+1 & \text { falls } n \text { ungerade ist; } \\ \lambda(n-2)+\lambda(n-1) & \text { falls } n \text { gerade ist und } n>0 \end{array}\right. $$

Zeigen Sie induktiv:

$$ \lambda(n)=\left\{\begin{array}{ll} 3 \cdot 2^{k} & \text { falls } n \text { ungerade ist, d.h. } \exists k \in \mathbb{N}: n=2 k+1 \\ 3 \cdot 2^{k}-1 & \text { falls } n \text { gerade ist, d.h. } \exists k \in \mathbb{N}: n=2 k \end{array}\right. $$

Problem/Ansatz:

Ist zu zeigen, dass $$3\cdot2^k=\lambda\left(n-1\right)+1$$ für n=2k+1 gilt und $$3\cdot2^k-1=\lambda\left(n-2\right)+\ \lambda\left(n-1\right)$$ für n=2k gilt? Und wie starte ich den Beweis? Ich habe auch noch nicht ganz verstanden, was \lambda ist und wie ich dann damit rechnen kann...

Answer 1

λ ist eine funktion von n, vielleicht nennst du es besser f(n)

du kennst f(0)=2  daraus f(1)=f(1-1)+1=2+1=3=3*2^0 denn k=0 wenn 2k+1=1

dann f(2)=f(0)+f(1)=2+3=5=3*2^1-1 beides richtig, jetzt von f(2k) und f(2k+1) auf f(2k+2) und f(2k+3) schleißen ist der Induktionsschritt.

Gruß lul

Comments

Vielen Dank lul. Ich habe das jetzt soweit aufgeschrieben, habe aber immer noch Probleme beim Induktionsschritt. Verändert sich $$3\cdot2^k $$ nicht? Ich hatte sonst die Idee, k als 0,5n-0,5 bzw. 0,5n zu definieren und dann im Induktionsschritt auch das um 1 zu erhöhen. Oder muss ich etwas anderes gleichsetzen? Zudem bin ich mir unsicher, wie ich die Induktionsvoraussetzung im Induktionsschritt mit einbaue.

Folgendes habe ich bisher aufgeschrieben:

Zu zeigen: $$\lambda\left(n-1\right)+1=3\cdot2^k$$ für n=2k+1 und $$\lambda\left(n-2\right)+\lambda\left(n-1\right)=3\cdot2^k-1$$ für n=2k
Induktionsanfang:
$$\lambda\left(0\right)=2$$ ist gegeben
Für n=1 gilt:
$$\lambda\left(1\right)=\lambda\left(n-1\right)+1 =\lambda\left(1-1\right)+1=\lambda\left(0\right)+1=2+1=3$$
Aus n=2k+1 und $$3\cdot2^k$$ folgt für n=1:
1=2k+1 => k=0
$$3\cdot2^0=3\cdot1=3$$
Somit stimmt die Aussage für n=1
Für n=2 gilt:
$$\lambda\left(2\right)=\lambda\left(n-2\right)+\lambda\left(n-1\right)=\lambda\left(2-2\right)+\lambda\left(2-1\right)=\lambda\left(0\right)+\lambda\left(1\right) = 2+3=5$$
Aus n=2k und $$3\cdot2^k-1$$ folgt für n=2:
2=2k => k=1
$$3\cdot2^1-1=3\cdot2-1=5$$
      Somit stimmt die Aussage für n=2
Induktionsvoraussetzung:
Die Aussage gilt für ein beliebig festes n. Wir zeigen, dass unter der Induktionsvoraussetzung die
Induktionsbedingung gilt.
$$\lambda\left(2k+1\right)=3\cdot2^k $$
$$\lambda\left(2k\right)=3\cdot2^k-1 $$


Induktionsbehauptung:
$$\lambda\left(2k+3\right)=3\cdot2^k $$
$$\lambda\left(2k+2\right)=3\cdot2^k-1$$
Induktionsschritt:
$$\lambda\left(2k+3\right)=3\cdot2^k$$
$$\lambda\left(2k+3\right)=\lambda\left(2k+1\right)$$ (Induktionsvoraussetzung)

---

Hallo

du gehst das falsch an. Schon die Induktionsvorsetzungen sind die 2 Formeln für n=2k+1 und n=2k

daraus schließt du aus der ungeraden  2k+1 und der geraden 2k auf die nächste gerade also von n=2k+1 und n=2k auf n+1=2k+2  mit Formel für gerades n dazu brauchst du ja die 2 davor

aus n=2k+2 auf die nächste ungerade 2k+3 mit der Formel für ungerade n da brauchst du ja nur die davor

(ungewohnt ist wahrscheinlich dass man immer 2 Schritte braucht und damit immer 2 Schritte weiter kommt.)

Gruß lul