Zeigen Sie, dass f(n) = 2 · n

Question

Aufgabe:

Es sei eine Funktion f(n) wie folgt rekursiv definiert
f(n) = 
      f(n − 1) + 4 · n − 2              n > 1
              2                                 n = 1
Zeigen Sie, dass f(n) = 2 · n^2
für alle positiven ganzen Zahlen gilt.

wie kann ich dies beweisen ?

Comments

Was bedeutet...
...Zeile 2: f(n) = (
...Zeile 3: f(n − 1) + 4 · n − 2 n > 1
.. Zeile 6: 2

---

\(f(n)=\begin{cases}f(n − 1) + 4 \cdot n − 2&\text{falls }n > 1 \\2&\text{falls }n=1\end{cases}\)

---

so wird gemeint

Answer 1

für alle positiven ganzen Zahlen gilt

Das schreit nach vollständiger Induktion.

Comments

Hmmh,

ich dächte, die Vorschrift besagt: \(f(1)=2=2\cdot 1^2\)??

Aber vielleicht kann ja Fragesteller mal sagen, wieweit sie sich mit vollständiger Induktion auskennt - oder noch besser mal etwas darüber nachlesen.

Gruß

---

Ja stimmt. Ich war von den ganzen Zahlen verwirrt.

---

induktionsschritt

Annahme:

f(n)=2n^2.

Behauptung:

f(n+1)=2(n+1)^2.

beweis

f(n+1)=f(n+1-1) + 4(n+1-2)

= f(n)+ 4(n-1)    An

=2n^2 +4(n-1) ausklammern und addieren

=2(n^2+2n-1) hier ist Problem da ich -1 statt +1 bekommen

=2(n-1)^2

---

f(n+1) = f(n+1-1) + 4(n+1-2)

f(n+1) = f(n+1-1) + 4(n+1) - 2

---

induktionsschritt

Annahme:

f(n)=2n^2.

Behauptung:

f(n+1)=2(n+1)^2.

beweis

f(n+1)=f(n+1-1) + 4(n+1)-2

= f(n)+ 4(n+1)-2    An

=2n^2 + 4n +4-2 ausklammern und addieren

=2(n^2+2n+1)

=2(n+1)^2

---

Ist richtig.