Zeige mittels vollständiger Induktion, dass für alle n∈ℕ: f(n) ≤ n+1 gilt.

Question

Aufgabe:⌊⌋

Gegeben ist folgende rekursive Funktion f:ℕ→ℕ mit

f(n)=1 für n=0 und

f(n)=f(⌊\( \frac{n}{2} \) ⌋)+f(⌊\( \frac{n}{3} \) ⌋) für n>0

Problem/Ansatz:

Zeige mittels vollständiger Induktion, dass für alle n∈ℕ: f(n) ≤ n+1 gilt.

Der Induktionsanfang ist einfach. Allerdings verstehe ich nicht, wie die Induktionsvoraussetzung genutzt werden kann, um zum Induktionsschluss zu kommen.

Answer 1

Hallo

du musst f([(n+1)/2] und f([(n+1)/3] mit f([(n)/2] und f([(n)/3] vergleichen  eventuell mit Fallunterscheifung, 2|n,3|n die Summe n unterscheiden sich um maximal 1

Gruß lul