Beweisen Sie per Induktion, dass fn=(2n-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)¹)/3 = 0

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

Induktionsschritt: n --> n+1

fn+1 = fn + 2fn-1

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

2ⁿ - (-1)ⁿ = 1/2·2ⁿ + (-1)ⁿ + 2·(1/4·2ⁿ - (-1)ⁿ)

2ⁿ - (-1)ⁿ = 1/2·2ⁿ + (-1)ⁿ + 1/2·2ⁿ - 2·(-1)ⁿ

2ⁿ - (-1)ⁿ = 2ⁿ - (-1)ⁿ

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ß!