Beweis durch induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei G(n) ein Gitter bestehend aus einer Zeile und n Spalten. Formal definieren wir G(n) als Menge von Kreuzungspunkten (x, y) in N × N und Linien, die diese Punkte verbinden, und zwar wie folgt: Sei {(x, y) : x, y ∈ N, 0 ≤ x ≤ n, 0 ≤ y ≤ 1} die Menge von Kreuzungspunkten von G(n). zwischen je zwei Kreuzungspunkten k1 und k2 verläuft eine Linie genau dann, wenn sich k1 und k2 in genau einer Koordinate um genau den Betrag
eins unterscheiden. Sei R(n) die Anzahl der verschiedenen Rechtecke mit nicht-leerem Flächeninhalt, die ins Gitter G(n) so gezeichnet werden können, dass jedes Rechteck sich aus Linien von G(n) zusammensetzt. Die folgende Abbildung zeigt alle möglichen Rechtecke, die in G(3) gezeichnet werden können. Insbesondere ist R(3) = 6.
Beweisen Sie durch vollständige Induktion nach n, dass f.a. n ∈ N>0 gilt: R(n) = n(n+1)/2 |
also ich probiere seit einer weile rum.
ich möchte im ind.schritt die 1 bei R (n+1) raus holen so dass ich dann auf einer seite nur R(n) habe, aber irgentwie klappt das net so gut
R(n+1) = (n+1) ((n+1)+1) /2
eigentlich müsste es doch so sein:
R(n)= ((n+1) ((n+1)+1) /2) * (n(n+1)/2)
aber das funktioniert net, also habe ich da rum experimentiert:
R(n)= ((n+1) ((n+1)+1) /2) * (n(n+1)/2 - (n+1))
dies ist auch falsch aber wir kommen der sache näher denn jetzt müsste man alles durch 2 teilen um auf das richtige ergebnis zu kommen aber das kann ich doch einfach so net, sonst hätte ich auch R(n)/2
also was soll ich tun????
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:45 Fr 11.11.2011 | | Autor: | Blech |
> ich möchte im ind.schritt die 1 bei R (n+1) raus holen so dass ich dann auf einer seite nur R(n) habe, aber irgentwie klappt das net so gut
$R(n+1) = [mm] \frac{(n+1) ((n+1)+1)}{2 } [/mm] = [mm] (n+2)\frac{n+1} [/mm] 2 = [mm] n\frac{(n+1)}{2} [/mm] + [mm] 2\frac{(n+1)}2=R(n)+(n+1)$
[/mm]
> eigentlich müsste es doch so sein:
> R(n)= ((n+1) ((n+1)+1) /2) * (n(n+1)/2)
???
R(n)=R(n+1)*R(n)?
Wieso das?
> aber das funktioniert net, also habe ich da rum experimentiert:
> R(n)= ((n+1) ((n+1)+1) /2) * (n(n+1)/2 - (n+1))
Ebenso.
Wenn Du schreiben würdest, wie Du auf Deine Formeln kommst, dann könnte ich Dir vielleicht sagen, wo Dein Denkfehler ist. =)
ciao
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:24 Fr 11.11.2011 | | Autor: | jess240890 |
ja also ich habe mir gedacht, dass ich das ganze wie ein summe betrachten soll, und wollte deshalb wie ich es bei einer Summe mache die 1 von n+1 raus hole.
ich kann mich gerade nicht besser ausdrücken, hoffe du hast mich trozdem verstanden.
mir ist auch aufgefallen dass die zu beweisende formel dies hier entspricht :
[mm] \summe_{i=1}^{n} [/mm] i
kann mir dies weiterhelfen?
in prinziep, was soll cih machen damit ich weiterkomme?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:06 Sa 12.11.2011 | | Autor: | Blech |
Hi,
> in prinziep, was soll cih machen damit ich weiterkomme?
Bei Induktion ist die Frage immer, was ändert sich von einem Schritt zum nächsten?
Du hast für Breite n alle Rechtecke abgezählt, jetzt vergrößerst Du die Breite um 1. Welche Rechtecke kommen neu dazu, die vorher noch nicht möglich waren?
ciao
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:18 Sa 12.11.2011 | | Autor: | jess240890 |
hi ich habe das jetzt so gemacht:
R (n) = [mm] \bruch{n+1}{2} [/mm] * n = [mm] \bruch{n^2 +n}{2}
[/mm]
R(n+1) = [mm] \bruch{n+2}{2} [/mm] * (n+1)
R(n+1)= [mm] \bruch{n^2+3n+2}{2} [/mm] = [mm] \bruch{n^2 +n}{2} [/mm] + [mm] \bruch{2n+2}{2}
[/mm]
[mm] \bruch{n^2 +n}{2} [/mm] können wir weg lassen gemäß R(n)
jetzt muss ich nur noch
[mm] \bruch{2n+2}{2} [/mm] beweisen...wie kann ich das tun?
habe
[mm] \bruch{2n+2}{2} [/mm] = [mm] \bruch{n+1}{2} [/mm] * 2
dies erinnert mich sehr an R(n) nur dass das n mit einer 2 ersetzt wird, aber weiter komme ich nicht
|
|
|
| |
|
hi ich habe das jetzt so gemacht:
R (n) = * n =
R(n+1) = * (n+1)
R(n+1)= = +
können wir weg lassen gemäß R(n)
jetzt muss ich nur noch
beweisen...wie kann ich das tun?
habe
= * 2
dies erinnert mich sehr an R(n) nur dass das n mit einer 2 ersetzt wird, aber weiter komme ich nicht
|
|
|
| |
|
hi ich habe das jetzt so gemacht:
R (n) = [mm] \bruch{n+1}{2} [/mm] * n = [mm] \bruch{n^2 + n}{2}
[/mm]
R(n+1) = [mm] \bruch{n+2}{2} [/mm] * (n+1)
R(n+1) = [mm] \bruch{n^2+3n+2}{2}
[/mm]
R(n+1) = [mm] \bruch{n^2+n}{2} [/mm] + [mm] \bruch{2n+2}{2}
[/mm]
[mm] \bruch{n^2+n}{2} [/mm] können wir weg lassen gemäß R(n)
jetzt muss ich nur noch dies beweisen:
[mm] \bruch{2n+2}{2}
[/mm]
= [mm] \bruch{n+1}{2} [/mm] * 2 = n+1
wäre dieser teil somit bewiesen???
ins gesamt hätten wir folgendes:
R(n+1) = [mm] \bruch{n^2+n}{2} [/mm] + (n+1)
oder auch so
R(n+1) = R(n) + (n+1)
dies erinnert mich sehr an R(n) nur dass das n mit einer 2 ersetzt wird, aber weiter komme ich nicht
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:51 Di 15.11.2011 | | Autor: | leduart |
hallo
1. musst du zeigen , dass die Formel für n=1 gilt!
Dann folgt die Beh. wenn sie für n gilt, dann auch für n*1
also R(n)=n*(n+1)/2 dann ist die Formel für n+1 Reihen:
R(n+1)=(n+1)*(n+2)/2 das ist die Behauptung
das hast du umgeformt zu R(n+1)=R(n)+(2n+2)/2=R(n)+(n+1)
((2n+2)/2=2(n+1)/2=n+1)
jetzt solltest du nur noch begründen warum wenn man eine weitere Reihe dazufügt man n+1 zusätzliche Rechtecke bekommt.Dann hast du die formel für die rechteckanzahl bewiesen!
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:34 Sa 12.11.2011 | | Autor: | jess240890 |
oh was habe ich da für ein mist geschrieben? weiss nicht mehr genau wie ich drauf gekommen bin o.0
|
|
|
|
