Beweis einer geraden/ungeraden Funktion durch Induktion

Question

$$\text{Hallo, man definiert } f:\mathbb{N}\backslash\{0\}\rightarrow\mathbb{N}\backslash\{0\}\newline f(n) := 0\text{ falls n = 1},\space 4f(\frac{n}{2}) + 3 \text{ falls n gerade},\space f(n-1)+2n-1\text{ sonst } \newline \text{Man soll jetzt mit Induktion die Behauptung beweisen, dass}\space \forall \space n \in \mathbb{N} \text{ mit } n \geq 1 \text{ gilt } f(n)=n^{2}-1 \newline \text{Induktionsanfang überspringe ich, Induktionsannahme:} \newline \text{Für ein festes, aber beliebiges } n \geq2 \text{ gilt } f(k)=k^{2}-1 \space \forall \space k\in \{1,...,n-1\} \newline \text{Induktionsschritt: }k\in \{1,...,n-1\}\rightarrow n \newline \text{1.Fall n gerade}\newline \Rightarrow f(n) = 4(\frac{n}{2}) + 3 = 4[(\frac{n}{2})^{2}-1]+3= n^{2} -1 \text{ Behauptung stimmt} \newline \text{2.Fall n ungerade}\newline \Rightarrow f(n)=f(n-1)+2n-1=(n-1)^{2}-1+2n-1= (...)\text{ Behauptung stimmt}$$
Ich hätte hierzu zwei Fragen:
$$\text{Woher kommt das} 4[(\frac{n}{2})^{2}-1]+3 \text{ in Fall 1 ? Also wie kommt man auf } (\frac{n}{2})^{2}-1 ? \newline \text{Und wie kommt man auf } (n-1)^{2} \text{in } (n-1)^{2}-1+2n-1 \text{ aus Fall 2 ? }$$
Danke im Voraus

Answer 1

Fall 1. Da fehlt ein $f$: $f(n) = 4{\color{green}{f}}\left(\frac n2\right) + 3$

Auf $k=\frac n2$ wird die Induktionsvoraussetzung angewendet. Es gilt also

$f\left(\frac n2\right) =\left(\frac n2\right)^2-1$

Fall 2. Hier wird auch die Induktionsvoraussetzung verwendet:
$f(n-1) = (n-1)^2-1$

Comments

Danke, macht Sinn.