Beweisen Sie per Induktion, dass fn=(2^{n-1}+(-1)^n)/3 für alle n ∈ N gilt.

Question

Wir definieren eine Folge (f_n)_n∈ℕ rekursiv:

f₁=0, f₂=1, f_n+1=f_n+2f_n-1

Beweisen Sie per Induktion, dass f_n=(2^n-1+(-1)ⁿ )/3 für alle n ∈ ℕ gilt.

Answer 1

Induktionsanfang n = 1 ; n = 2

f1 = (2^{1 - 1} + (-1)^1)/3 = 0

f2 = (2^{2 - 1} + (-1)^2)/3 = 1

Induktionsschritt: n --> n+1

fn+1 = fn + 2fn-1

(2^ ((n + 1) - 1) + (-1)^{n + 1})/3 = (2^{n - 1} + (-1)^n)/3 + 2·(2^ ((n - 1) - 1) + (-1)^{n - 1})/3

2^n - (-1)^n = 1/2·2^n + (-1)^n + 2·(1/4·2^n - (-1)^n)

2^n - (-1)^n = 1/2·2^n + (-1)^n + 1/2·2^n - 2·(-1)^n

2^n - (-1)^n = 2^n - (-1)^n

wzbw.

Comments

Hey Mathecoach,

im letzten Teil ab :"(2^ ((n + 1) - 1) + (-1)^{n + 1})/3 = (2^{n - 1} + (-1)ⁿ)/3 + 2·(2^ ((n - 1) - 1) + (-1)^{n - 1})/3" wird im nächsten Schritt das + (-1) zu -(-1) und es kommt auf einmal ein 1/4 her. 

Diese 2 Punkte habe ich noch nicht so ganz verstanden.

Schönen Gruß!