Rekursive Folge beweisen

Question

Wir definieren eine rekursive Folge( f_n )n∈N rekursiv:

f_{0:= 0 ;} f₁ :=1; f_n+1 :=f_n + 2f_n-1 

^{Beweisen Sie per Induktion dass}

^f_n= (2^n-(-1)ⁿ)/3 für alle n∈N

Hinweis: Überprüfen Sie diese Formel für n=0 und n=1. Dann setzen Sie Voraus, dass sie für n=k und n=k-1 gilt und beweisen, dass diese Formel für n=k+1 gilt. Dabei ist x^0=1 für alle x∈ℝ 

Comments

Das n in der zu beweisenden Formel steht jeweils im Exponenten. 

Answer 1

Induktionsanfang: n = 0 und n = 1

f0 = 1/3·(2^0 - (-1)^0) = 0

f1 = 1/3·(2^1 - (-1)^1) = 1

Induktionsschritt: Aus n - 1 und n folgt n + 2

fn + 2·fn-1 = fn+1

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

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

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

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

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

Das war zu zeigen.

Comments

Vielen Dank für die ausführliche Antwort!

Answer 2

für den Induktionsanfang setzt du n = 0, und n = 1 und kriegst mit der Formel f₀ = 0 und f₁ = 1 raus.

Für den Induktionsschritt (mal was anderes), ist die Voraussetzung, dass die Formel für n und n-1 gilt. Wir wollen zeigen, dass sie für n+1 auch gilt

$$ f_{n+1} = f_n + 2f_{n-1} =  \frac{2^n - (-1)^n}{3} + 2 \cdot\frac{2^{n-1} - (-1)^{n-1}}{3}$$

jetzt nur noch zusammen verrechnen und auf die Form

$$ f_{n+1} = \frac{2^{n+1} - (-1)^{n+1}}{3} $$

bringen.

Gruß

Comments

Vielen Dank für die ausführliche Antwort!