Mit Induktion zeigen, dass rekursive Folge mit expliziter Folge übereinstimmt

Question

habe hier folgendes Problem, dass ich per vollständigen Induktion zeigen soll, dass eine rekursive Folge mit einer expliziten übereinstimmt. Ich weiß zwar wie ich generell Induktion auf die Folge anwende um beispielsweise zu zeigen, dass sie konvergent etc ist, aber ich weiß nicht wie ich es anstellen soll, dass ich per Induktion die Gleichheit der Folgen beweisen soll :/

a_n+1 = 1/2 a_n + 1/2       für      n >= 1   (mit a₀ = 0)

und

b_n = (2ⁿ - 1) / 2ⁿ    für     n >= 0

Bin für jeden Tipp dankbar :)

Answer 1

bn = (2^n - 1)/2^n = 1 - 2^{-n}

Induktionsanfang

Zeige dass

a0 = b0

Induktionsschritt

an+1 = bn+1

1/2·an + 1/2 = 1 - 2^{-[n+1]}

1/2·bn + 1/2 = 1 - 2^{-n-1}

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

1 - 2^{-n - 1} = 1 - 2^{-n - 1}

wzbw.