$$ \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
