# Vollständige Induktion für Java-Methode



## User5001 (1. Feb 2011)

Ich weiß nicht so recht, ob ich hier im Forum richtig bin mit meiner Frage, versuche es aber trotzdem mal 

Folgende Aufgabe gilt es zu lösen:







Der Quellcode dazu ist dieser:


```
public static double calc (int n) {
	if (n < 0)
		throw new RuntimeException ();
	double summe = 0.0;
	int produkt = 1;
	double quotient = 0.0;
	int i = 0;
	// I
	while(i < n) {
		i++;
		produkt = i * (i +1);
		quotient = 1.0/ produkt ;
		summe += quotient ;
		// II
	}
	return summe ;
}
```

Meiner Überlegung nach ist jetzt summe = summe + 1.0 / produkt was ja summe = summe + 1.0 / i * (i+1) ist.
Das ist ja was anderes als zu beweisen ist. ???:L Hat jemand eine Idee, wie man die Sache angeht?


----------



## SlaterB (1. Feb 2011)

ein wichtiger Punkt bei Induktion ist, dass du annehmen kannst, dass für den vorherigen Schritt die Annahme stimmt (für den ersten ja bewiesen),
(edit: steht ja auch groß und breit in der Aufgabe, bei b) die ersten zwei Zeilen.. )
daher ist summe nicht irgendwas beliebiges sondern genau ein Term den du zum Ausrechnen brauchst, 
du musst den alten Term einsetzen und bekommst den neuen der auch wieder stimmt


----------



## Gonzo17 (1. Feb 2011)

Naja ich würde bei solchen Aufgaben immer den "mathematischen Weg" gehen, indem ich aus dem Code abeschreibe, was mathematisch so enthalten ist. Da steht ja beispielsweise nichts anderes als 
	
	
	
	





```
summe(n+1) = summe(n) + quotient(n)
```
 (oder so in der Art). Musst du dir dann eben mal weitere Gedanken machen und dann kommste auch drauf.


----------



## Andi_CH (1. Feb 2011)

Was ist eine Schleifeninvariante? Die einzige Variable die von der Schleife nicht verändert wird ist der Parameter n. Muss man beweisen das "n" stimmt? 

Summe = Schleifen*in*variante ???:L

Warum wird so etwas in einem loop berechnet?


```
return ((n*1.0) / n + 1.0);
```

reicht doch auch?

Vermutlich wäre das im Bereich Mathematik besser aufgehoben? Ich sehe kein Java-typisches Problem ausser einer unhandlich komplizierten Lösung für eine banales Problem.


----------



## User5001 (1. Feb 2011)

Danke für die Tipps! 

Ja, mit Java hat das nicht unbedingt zu tun, ist nur das erste mal, dass ich einen Beweis zu einem Quelltext mache und ich dachte, hier hat das der ein oder andere schon hinter sich und kann helfen.

Ich denke, ich habs jetzt. Falls es jemanden interessiert, hier mein Versuch einer Lösung (mangels Zeit in Form von Screenshots):


 

 



Ich hoffe das kommt in etwa hin. Die Tabellen sind wohl nicht unbedingt notwendig, bringen aber vielleicht ein paar Pünktchen bei der Korrektur.


----------



## SlaterB (1. Feb 2011)

bisher hast du keinen Beweis,
du schreibst zunächst immer noch
summe = summe + 1/(i*(i+1))
was als Java-Befehl vielleicht Sinn macht, in der Mathematik aber nicht, summe links ist was anderes als summe rechts, also vergib auch unterschiedliche Variablen, wie Gonzo17 schon schrieb z.B. summe_i, summe_i+1 usw
das Einsetzen danach ist falsch bis fragwürdig, 

besonders danach dann aber "was genau [..] entspricht" ist nun kein Beweis sondern eine Behauptung,
eine nicht richtige dazu, durch Beispiel (i = 5 einsetzen) leicht zu widerlegen


----------



## Andi_CH (1. Feb 2011)

User5001 hat gesagt.:


> Ja, mit Java hat das nicht unbedingt zu tun, ist nur das erste mal, dass ich einen Beweis zu einem Quelltext mache und ich dachte, hier hat das der ein oder andere schon hinter sich und kann helfen.



Du sollst eine beliebige Funktion beweisen, die im Quellcode vorliegt - was ich sagen wollte: Das Forum ist defintiv nicht das optimale das ist eine rein Mathematische Problemstellung.

Ich hab mir eben erklären lassen (ja und die grauen Zellen ganz weit hinten erwachten dann auch wieder=) was ein Induktion ist.

1. Schritt
Es gilt zu Beweisen, dass die Funktion für einen bestimmten Wert x das richtige Resultat liefert.
Ist in diesem Fall für X = 0 recht einfach
Mathematisch: f(0) = 0 / 0+1 = 0;
Die Funktion liefert 0, da der loop nie durchlaufen wird.
Des paasst

2. Schritt
Es gilt zu beweisen, dass die Funktion für ein beliebiges n ein korrektes Resultat liefert welches auf n-1 basiert. 
Die Summe enthält das Resultat der letzten Berechung, also f(n-1)
Der Quotient enthält 1 / n * (n +1)
f(n) =  n / (n+1) = f(n-1) +  ( 1 / n * (n +1)) = summe + quotient

Für n = 4 (Beliebig gewählt - halt so dass es einfach Brüche gibt  )

Direkt gerechnet: f(n) = n/(n+1) = 4/5

Basierend auf n-1 gerechnet:
f(n-1) = 3/4;
(1/(n*(n+1)) = 1 / 20
f(n) = 3/4 + 1/20 = 16/20 = 4/5 = f(n) qed

Ist es das was der Prof sehen will?


----------



## SlaterB (1. Feb 2011)

gesehen werden will ein allgemeiner Beweis mit Variablen, nicht ein bestimmtest Beispiel 4 und 5,
aber ein ganz guter Hinweis zum Rechnungsweg ohne gleich alles zu lösen, insofern passt das schon


----------



## Andi_CH (1. Feb 2011)

Die Vollständige Induktion basiert aber genau auf einem konkreten Wert als Anfangsbedingung und dem Schritt von N auf N+1 ....

Jetzt kann ja auf dem Papier schritt für schritt nachweisen, dass das auch formelgemäss implementiert ist.

Mindestens für mich war erst mal der Beweis fällig, dass man n/n+1 auch wirklich so berechnen kann, wobei das allerdings viele einfacher auf algebraischem Weg denn als Induktion geht ....

Ich bin allerdings extrem gespannt wie man so einen Beweis anhand von Code führen soll.


----------



## User5001 (2. Feb 2011)

Danke für die ganzen Tipps. Letztendlich hats doch noch hingehauen (hoffe ich)


----------



## Andi_CH (2. Feb 2011)

... und jetzt lässt du uns (im Speziellen mich) unwissend hängen? ... oder muss ich auf die Musterlösung warten? ;-)


----------



## User5001 (3. Feb 2011)

Erstmal abwarten, wie gut meine Lösung war, dann kann ich sie auch gerne posten (dazu muss mein Prof sie mir aber erstmal zurückgeben)


----------



## User5001 (9. Feb 2011)

Andi_CH hat gesagt.:


> ... und jetzt lässt du uns (im Speziellen mich) unwissend hängen? ... oder muss ich auf die Musterlösung warten? ;-)



So, falls es noch interessiert, hier meine Lösung:



 

 

Es gab volle Punktzahl. Wobei die Form noch etwas schicker sein könnte (hatte keine Zeit mehr)...


----------



## SlaterB (9. Feb 2011)

i/(i+1) + 1/((i+1)*(i+2))
= (i+1)/(i+2)

genau, das ist der entscheidende Schritt, 
erstaunlich dass du volle Punktzahl bekommst obwohl du ihn nur einfach hingeschrieben hast 

die Umrechnungen dafür sind gar nicht so trivial, mit binomischer Formel,
jedenfalls aus mathematischer Sicht interessanter als die restlichen 2 Seiten der Lösung


----------



## User5001 (9. Feb 2011)

Ja, die Tabellen usw. waren wohl garnicht nötig, aber lieber zu viel als zu wenig, solange es nicht falsch ist.
Evtl. ist die Bewertung in meinem Fall nicht so streng. Ich studiere eigentlich Biologie und kämpfe mich nur durch ein unbenotetes Informatik-Modul um der Studienordnung gerecht zu werden.


----------

