Induktionsbeweis oder was? < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:15 So 30.10.2005 | | Autor: | Chapo1 |
Hallo, ich weiss dass ich jetzt zu später stunde reinschreibe, aber leider hab ich keine andere wahl. Ich wollte nämlich zuerst alleine versuchen diese Aufgabe zu lösen, aber komme ich noch nichtmal zu einem Ansatz!
So lautet die Aufgabe:
Zeigen Sie, dass man [mm] a[(a^n)-1]/[a-1] [/mm] Kombinationen der Länge mindestens 1 und höchstens n bilden kann.
Ich wäre dankbar für jede Lösung/Rat/Tipp/Vorschlag/Hilfe.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> Hallo, ich weiss dass ich jetzt zu später stunde
> reinschreibe, aber leider hab ich keine andere wahl.
> So lautet die Aufgabe:
> Zeigen Sie, dass man [mm]a[(a^n)-1]/[a-1][/mm] Kombinationen der
> Länge mindestens 1 und höchstens n bilden kann.
Hallo,
Kombinationen wovon denn, bitteschön? Das müßte man schon erklären...
Na, seiest Du durch "späte Stunde" entschuldigt, und da gerade frühe Stunde ist, kann ich es ahnen: gewiß hast Du a Zahlen oder a Farben, jedenfalls a zu kombinierende Objekte.
Nehmen wir mal ein Beispiel. 3 Zahlen, aus denen alle Kombinationen der Lange 1,2,3,4,5 gebildet werden sollen und die Gesamtzahl bestimmt.
Länge 1 : 3 Möglichkeiten
Länge 2 : [mm] 3^2 [/mm] Möglichkeiten
Länge 3 : [mm] 3^3 [/mm] Möglichkeiten
Länge 4 : [mm] 3^4 [/mm] Möglichkeiten
Länge 5 : [mm] 3^5 [/mm] Möglichkeiten
Also insgesamt [mm] 3++^1+3^2+3^3+3^4+3^5 [/mm] Möglichkeiten.
Nun könntest Du mal überprüfen, ob das der zu beweisenden Aussage entspricht. Ist [mm] 3++^1+3^2+3^3+3^4+3^5=[/mm] [mm]3[(3^5)-1]/[3-1][/mm]?
Nach dieser Vorübung fällt es Dir sicher nicht mehr schwer, einen Ausdruck für die Anzahl der 1 bis n langen Kombinationen von a Dingen zu finden.
Deine zu beweisende Behauptung ist dann ...= [mm]a[(a^n)-1]/[a-1][/mm]
Das geht in der Tat mit Induktion, aber wenn ich Dich recht verstehe, war es nicht die Induktion als solche an der Du gescheitert bist.
Gruß v. Angela
>
> Ich wäre dankbar für jede Lösung/Rat/Tipp/Vorschlag/Hilfe.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:28 So 30.10.2005 | | Autor: | oeli1985 |
Hallo zusammen,
also ich muss die selbe Aufgabe lösen! Es geht zunächst darum, dass es ein Alphabet mit a=26 Buchstaben gibt, wobei a [mm] \varepsilon \IN [/mm] ist. Nun soll man eine Formel für die Anzahl aller möglichen (sinvolle und sinnlose) Wörter der Länge n aufstellen.
Meine Lösung dazu: n! * [mm] a^{n}
[/mm]
Jedoch bin ich inzwischen soweit, dass ich denke nicht beachtet zu haben, dass z.B. die Kombination eines sinnlosen Worts, welches ausschließlich aus ein und dem selben Buchstaben besteht mehrfach kombiniert werden kann. Man kann ja z.B. anfangen die n-Plätze von vorne oder von hinten zu belegen (die Reihenfolge ist hier ja nicht zu beachten), das wären dann schon 2 Möglichkeiten!?
Jedenfalls habe ich dann mit vollständiger Induktion versucht zu zeigen, dass
[mm] \summe_{k=1}^{n} [/mm] n! * [mm] a^{n} [/mm] = a( [mm] a^{n} [/mm] - 1) / (a - 1)
ist. Dazu ist der Induktionsanfang mit n=1 richtig, aber beim Induktionsschritt bin ich an folgender Stelle gescheitert:
a * [ [mm] a^{n} [/mm] + ( [mm] a^{n+1} [/mm] * (n+1)! - [mm] a^{n} [/mm] * (n+1)! ) - 1] / a - 1
z.zg. habe ich nun ja, dass der Zähler:
a * ( [mm] a^{n+1} [/mm] - 1)
ist bzw. dass der Ausdruck in der inneren Klammer:
[mm] a^{n+1} [/mm] - [mm] a^{n} [/mm]
ist.
Der Fehler wird wahrscheinlich daran liegen, dass ich die Möglichkeit der mehrfach auftretenden Kombinationen nicht beachtet habe. Wenn das stimmt könnt ihr mir diesbezüglich weiterhelfen und ansonsten bezüglich des Induktionsschritts? Danke schonmal.
Gruß, Patrick
|
|
|
| |
|
> Hallo zusammen,
> also ich muss die selbe Aufgabe lösen!
Es geht zunächst
> darum, dass es ein Alphabet mit a=26 Buchstaben gibt, wobei
> a [mm]\varepsilon \IN[/mm] ist. Nun soll man eine Formel für die
> Anzahl aller möglichen (sinvolle und sinnlose) Wörter der
> Länge n aufstellen.
>
> Meine Lösung dazu: n! * [mm]a^{n}[/mm]
Das ist nicht richtig.
Wenn Du a Buchstaben hast,
hast Du für den ersten Platz a Möglichkeiten, für den zweiten Platz a Möglichkeiten, ebenso für den dritten, ..., und auch für den n-ten Platz hast Du a Buchstaben zur Auswähl.
Also kannst Du aus a Buchstaben [mm] a^n [/mm] Wörter bilden. Die sind alle verschieden. Wir sind die Bildung der Wörter absolut systematisch von vorne nach hinten angegangen.
Und wo nun die Anzahl der Möglichkeiten für die Wortlänge n stimmt, bin ich optimistisch, daß Du beim Aufsummieren zum richtigen Ergebnis kommst.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:39 So 30.10.2005 | | Autor: | oeli1985 |
Hört sich logisch an.
Aber warum genau gehe ich systematisch von vorne nach hinten? Sind nicht auch andere Reihenfolgen möglich, da ja letztlich immer alle Plätze belegt werden und so ein Wort entsteht?
DANKE
|
|
|
| |
|
> Hört sich logisch an.
>
> Aber warum genau gehe ich systematisch von vorne nach
> hinten? Sind nicht auch andere Reihenfolgen möglich, da ja
> letztlich immer alle Plätze belegt werden und so ein Wort
> entsteht?
Klar. Wenn Du möchtest, kannst du jede Reihenfolge nehmen, sofern Du nicht den Überblick verlierst. Fein jeden Platz nur einmal belegen. Wie auch immer Du es machst, es bleiben [mm] a^n [/mm] Möglichkeiten.
(Ich glaub', Du mußt Dir wegen "Reihenfolge" keine grauen Haare an den Kopf denken. Bestimmt hast Du noch furchtbar viel anderes zu tun...)
Hast du die Induktion denn schon durchgeführt? Klappt's?
Gruß v. Angela
|
|
|
|
