Zeigen Sie mit Hilfe der vollständigen Induktion

Question

Die rekursiv definierte Folge a₁ = 5 , a_n+1 = 2a_n + 1 hat für n∈ℕ die explizite Darstellung a_n = 2ⁿ⁺¹ + 2ⁿ - 1.

Answer 1

Induktionsanfang ist klar.

Induktionsschluss: Aus der Induktionsvoraussetzung a_n = 2ⁿ⁺¹ + 2ⁿ - 1 ist die Induktionsbehauptung zu folgern a_n+1 = 2ⁿ⁺² + 2ⁿ⁺¹ - 1.

Außerdem ist a_n+1 = 2a_n + 1. Hier Einsetzen der Induktionsvoraussetung ergibt a_n+1 = 2(2ⁿ⁺¹ + 2ⁿ - 1) + 1 und dann umformen zu a_n+1 = 2ⁿ⁺² + 2ⁿ⁺¹ - 1. Was zu zeigen war.