Verallgemeinerte Induktion, vollständige Induktion

Question

1. Eine Folge a0, a1, ... von natürlichen Zahlen sei wie folgt definiert:

a0 = 0

a1 = 1

a2 = 1

an = 1/2 an -3 + 3/2an -2 + 1/2an -1  für n >= 3.

Zeigen Sie, dass für alle n E natürlichen Zahlen gilt an = fib(n). fib bezeichnet Fibonacci-Funktion.

2. Zeigen Sie mittels vollständiger Induktion, dass für alle n E natürlichen Zahlen gilt:

n^2 + n + 2 ist gerade.

Answer 1

2.

Zu zeigen:

n^2 + n + 2 ist gerade

Induktionsanfang: n = 0

0^2 + 0 + 2 ist gerade
2 ist gerade --> stimmt

Induktionsschritt: n --> n + 1

(n + 1)^2 + (n + 1) + 2 ist gerade
n^2 + 2n + 1 + n + 1 + 2 ist gerade
(n^2 + n + 2) + (2n + 2) ist gerade
(n^2 + n + 2) + 2(n + 1) ist gerade
n^2 + n + 2 ist durch die Induktionsvoraussetzung gerade
2(n + 1) enthält den Faktor 2 und ist daher auch gerade
Die Summe zweier gerader Zahlen ist wieder eine gerade Zahl.
stimmt

Comments

Fibonacci ist wie folgt definiert

a(n) = a(n-1) + a(n-2)

a(n) = 1/2 * a(n-1) + 1/2 * a(n-1) + a(n-2)

a(n) = 1/2 * a(n-1) + 1/2 * (a(n-2) + a(n-3)) + a(n-2)

a(n) = 1/2 * a(n-1) + 1/2 * a(n-2) + 1/2 * a(n-3) + a(n-2)

a(n) = 1/2 * a(n-1) + 3/2 * a(n-2) + 1/2 * a(n-3)

Dann konnten wir aus der Definition für die Fibonacci-Folge unsere Folgendefinition herleiten.