Vollständige Induktion rekursiv

else

Hallo,

hab beim lernen gerade eine Aufgabe gefunden, an der ich jetzt schon länger hänge...
Gegeben Sei folgende Methode f:
long f(int a, int u, int d) {if (d == 1) {
return a;
} else if (d == 2) {
return 2 * a + u;} else {
return f(a, u, d - 2) + 2 * a + 2 * d * u - 3 * u;}
}
Beweisen Sie formal mittels vollständiger Induktion:∀d≥1:f(a,u,d)≡ (d(2a+(d-1)u)/2

wäre nett, wenn mir jemand auf die Sprünge helfen könnte.

MfG Elsa

Bradon

Hat ja eher weniger mit Programmieren zu tun..

Induktionsanfang: d=1
f(a,u,d) = (1*(2a+(1-1)u))/2 (ich nehme an, die fehlende Klammer gehoert so gesetzt)
a = 2a/2
a = a

Spezialfall d=2:
f(a,u,d) = 2(2a+(2-1)u)/2
2a+u = 2a+u

Induktionsschritt: d > 2
f(a,u,d) = d(2a+(d-1)u)/2
f(a,u,d-2) + 2a+2du-3u = da + d(d-1)u/2
(d-2)(2a+(d-3)u)/2 + 2a + 2du - 3u = da + d(d-1)u/2
da + d(d-3)u/2 - (2a + (d-3)u) + 2a + 2du - 3u = da + d(d-1)u/2
(d^2)u/2 - 3du/2 - 2a - du + 3u + 2a + 2du - 3u = (d^2)u/2 - du/2
[strike](d^2)u/2[/strike] - 3du/2 [strike]- 2a[/strike] - du [strike]+ 3u[/strike] [strike]+ 2a[/strike] + 2du [strike]- 3u[/strike] = [strike](d^2)u/2[/strike] - du/2
-3du/2 - du + 2du = -du/2
-du/2 = -du/2

q.e.d.

Christoph R.

Für d=1:
a = 1(2a+(1-1)u)/2 nachrechnen

Für d=2: dasselbe mit 2a+u.

Für d>=2:
f(a, u, d) = f(a, u, d-2) + 2 * a + 2 * d * u - 3 * u => laut Induktionsvoraussetzung => ((d-2)(2a + (d-2 - 1)u))/2 + 2a + 2du - 3u => umformen => (4a + 4du - 6u + (d-2)(2a + du - 3u))/2 = (2du + (d-2+2)(2a + du - 3u))/2 = (2du + d(2a + u(d - 3)))/2 = (d(2a+(d-1)u)/2

Edit: Da war wohl einer schneller. Und schöner hat er's auch noch gemacht. :devil:

Jetzt mitmachen!