Induktion, Folge, Rekursion, konkretes Bsp! Behauptung: xk = 2 * (-2)^k - 1

Question

Ich bin eig nicht schlecht darin, Sachen induktiv zu beweisen, aber mit dieser Aufgabe habe ich Probleme. Und da ich morgen Test hab, wäre es super, wenn mir wär behilflich sein könnte.... hierbei:

Eine Folge sei gegeben:

x₀ = 1  x₁= -5

x_k+1 = -x_k + 2_k-1

Zeigen Sie durch Induktion, dass x_k = 2*(-2)^k - 1

 

Answer 1

x_k+1 = -x_k + 2*x_k-1

Vermutung:

x(k) = 2*(-2)^k - 1

Wir zeigen, dass es für k=0 und k=1 gilt:

x(0) = 1

x(1) = -5

Das stimmt. Nun zeige ich das es für k+1 gilt unter der Annahme, dass es für k gilt.

x(k+1) = -x(k) + 2*x(k-1)

-1 - 2^{k + 2}·(-1)^k = -(2^{k + 1}·(-1)^k - 1) + 2*(-1 - (-2)^k)

-1 - 2^{k + 2}·(-1)^k = -(2^{k + 1}·(-1)^k - 1) + 2*(-1 - (-2)^k)

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

Damit ist es gezeigt.