Produkt von n nat. Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:08 Di 11.12.2012 | | Autor: | anig |
| Aufgabe | Das Produkt von n aufeinanderfolgenden natürlichen Zahlen ist
durch n! teilbar. |
Ich bin mir nicht sicher, wie ich das beweisen soll?? Könnt ihr mir bitte konkrete Tipps geben??
Danke schonmal
|
|
| |
|
Hallo anig,
eine trickreiche Aufgabe...
> Das Produkt von n aufeinanderfolgenden natürlichen Zahlen
> ist durch n! teilbar.
>
> Ich bin mir nicht sicher, wie ich das beweisen soll??
> Könnt ihr mir bitte konkrete Tipps geben??
Betrachte alle Primzahlen [mm] \le{n}. [/mm] In welcher Potenz sind sie jeweils in n! enthalten?
Dann zeige, dass sie mindestens in gleicher Potenz auch in dem zu betrachtenden Produkt vorkommen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:09 Di 11.12.2012 | | Autor: | fred97 |
> Das Produkt von n aufeinanderfolgenden natürlichen Zahlen
> ist
> durch n! teilbar.
> Ich bin mir nicht sicher, wie ich das beweisen soll??
> Könnt ihr mir bitte konkrete Tipps geben??
Sei k [mm] \in \IN.
[/mm]
Zeige durch einfaches ausrechnen, dass für n [mm] \in \IN [/mm] gilt:
$ [mm] \vektor{k+n\\ n}*n!= [/mm] (k+1)(k+2)*...*(k+n)$
FRED
> Danke schonmal
|
|
|
| |
|
moin,
Auch wenn du bereits einige Hinweise hast, hier nochmal eine weitere Möglichkeit:
Zeige mittels vollständiger Induktion nach $m [mm] \in \IN$:
[/mm]
In der Menge der Zahlen $M = [mm] \{m,m+1,m+2,\ldots , m+n-1\}$ [/mm] gibt es für jede der Zahlen aus der Menge $N = [mm] \{1,2,\ldots , n\}$ [/mm] eine Zahl, die dadurch teilbar ist.
Oder genauer:
Es gibt eine bijektive Abbildung $f: N [mm] \to [/mm] M$, sodass $n [mm] \mid [/mm] f(n)$ für alle $n [mm] \in [/mm] N$.
Daraus folgt dann insbesondere auch deine Aussage.
Im Induktionsschluss würde ich dir raten so vorzugehen:
Sei $f : M [mm] \to [/mm] N$ besagte bijektive Abbildung aus der Induktionsvoraussetzung.
Betrachte die Menge [mm] $\tilde{M} [/mm] = [mm] \{m+1,m+2,\ldots , m+n\}$ [/mm] und definiere $g : N [mm] \to \tilde{M}$ [/mm] wie folgt:
$g(n) = f(n)$ für alle $n [mm] \in [/mm] N$ mit $f(n) [mm] \neq [/mm] m$ sowie
[mm] $g(f^{-1}(m))=m+n$.
[/mm]
Rechne nach, dass $g$ die gewünschten Eigenschaften hat.
lg
Schadow
PS: Der Vorschlag von fred ist natürlich deutlich schöner, falls du schon Binominalkoeffizienten kennst und insbesondere schon weißt, dass sie immer natürliche Zahlen oder $0$ sind.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:24 Di 11.12.2012 | | Autor: | felixf |
Moin!
> Es gibt eine bijektive Abbildung [mm]f: N \to M[/mm], sodass [mm]n \mid f(n)[/mm]
> für alle [mm]n \in N[/mm].
Ich glaube, diese Aussage stimmt nicht.
Sei etwa $n = 4$ und $m = 4$. Dann ist $N = [mm] \{ 1, 2, 3, 4 \}$ [/mm] und $M = [mm] \{ 4, 5, 6, 7 \}$. [/mm] Du musst 4 auf 4 zuordnen, und 2 und 3 beide auf 6. Damit ist die Abbildung aber nicht mehr injektiv.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:28 Di 11.12.2012 | | Autor: | felixf |
Moin!
Eine Anmerkung noch:
> > Es gibt eine bijektive Abbildung [mm]f: N \to M[/mm], sodass [mm]n \mid f(n)[/mm]
> > für alle [mm]n \in N[/mm].
Diese Aussage kannst du reparieren, indem du mit Primzahlen arbeitest: ist $p$ eine Primzahl und [mm] $\nu_p [/mm] : [mm] \IZ \setminus \{ 0 \} \to \IN$ [/mm] die $p$-adische Bewertung, also [mm] $\nu_p(a p^k) [/mm] = k$ falls $p [mm] \nmid [/mm] a$, so gilt folgendes (wenn ich mich richtig erinnere):
Zu jedem $n$, $m$, $p$ gibt es eine Bijektion $f : N [mm] \to [/mm] M$ mit [mm] $\nu_p(f(x)) \le \nu_p(x)$ [/mm] fuer alle $x [mm] \in [/mm] N$.
(Ich muss nochmal nachschauen ob ich das wiederfinde. Ich hatte mich damit mal im Rahmen eines Seminarvortrags beschaeftigt, hab meine Unterlagen dazu aber grad nicht da...)
Daraus folgt, dass der $p$-Anteil von $n!$ das Produkt $m [mm] \cdot [/mm] (m+1) [mm] \cdots [/mm] (m+n-1)$ teilt. Dies impliziert insbesondere die Aussage von reverend.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:14 Di 11.12.2012 | | Autor: | anig |
Seid ihr sicher, dass diese Ansätze richtig sind?? Immerhin soll ich zeigen, dass die nat. zahlen durch n! teilbar sind nud nicht,dass sie so definiert werden. Bin mir da nicht so sicher.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:20 Di 11.12.2012 | | Autor: | felixf |
Moin!
> Seid ihr sicher, dass diese Ansätze richtig sind??
Die Ansaetze von reverend und fred97 sind korrekt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:42 Di 11.12.2012 | | Autor: | anig |
ok. Gut dann der Ansatz von fred wäre dann: [mm] \vektor{k+n\\n}*n!=(k+1)*(k+2)*... [/mm] (k+n).
Dann kann ich für die linke seite schreiben: [mm] \bruch{(k+n)!}{n!*(k+n-k)!}*n! [/mm] und das wiederrum ist gekürzt: [mm] \bruch{(k+n)!}{n!}
[/mm]
Und jetzt ist das Problem, dass auf der rechten seite nur(k+1)(k+2)*...(k+n) steht. Wo liegt denn da der Fehler??
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:54 Di 11.12.2012 | | Autor: | anig |
also habe noch mal nachgerechnet: ich habe dann [mm] \bruch{(k+n)!}{k!}
[/mm]
Ist das das gleiche wie (k+1)(k+2)...*(k+n)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:58 Di 11.12.2012 | | Autor: | Marcel |
Hallo,
Du hattest den Fehler ja gefunden:
> ok. Gut dann der Ansatz von fred wäre dann:
> [mm]\vektor{k+n\\n}*n!=(k+1)*(k+2)*...[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
(k+n).
diese Gleichheit wäre zu zeigen - wobei sie sowieso schnell folgt:
$${k+n \choose n}=\frac{(k+n)!}{n!*k!}=\frac{\red{\produkt_{m=1}^{k+n} m}}{n!*\red{\produkt_{r=1}^{k}r}}}=\frac{\produkt_{m=k+1}^{k+n} m}{n!}$$
> Dann kann ich für die linke seite schreiben:
> [mm]\bruch{(k+n)!}{n!*(k+n-k)!}*n![/mm] und das wiederrum ist
> gekürzt: [mm]\bruch{(k+n)!}{n!}[/mm]
Das war falsch, richtig wäre:
$${k+n [mm] \choose n}=\frac{(k+n)!}{n!*(k+n\red{-n})!}\,.$$
[/mm]
P.S. Fred will wohl 'das Wissen' verwenden, dass Binomialkoeffzienten der
genannten Form halt [mm] $\in \IN_0$ [/mm] sind: Ist das denn bekannt? Ansonsten
drehen wir uns ein wenig im Kreise - es sei denn, Du kannst das auch
mit kombinatorischen Argumenten beweisen! (Denn prinzipiell ist für mich
erstmal nur die zu zeigende Aussage äquivalent damit, zu zeigen, dass
${k+n [mm] \choose [/mm] k} [mm] \in \IN_0$ [/mm] (oder [mm] $\IZ$) [/mm] gilt... oder übersehe ich da
etwas?)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:06 Di 11.12.2012 | | Autor: | felixf |
Moin Marcel,
> P.S. Fred will wohl 'das Wissen' verwenden, dass
> Binomialkoeffzienten der
> genannten Form halt [mm]\in \IN_0[/mm] sind: Ist das denn bekannt?
> Ansonsten
> drehen wir uns ein wenig im Kreise - es sei denn, Du
> kannst das auch
> mit kombinatorischen Argumenten beweisen!
ich wuerde es mit der Additionsformel fuer Binomialkoeffizienten beweisen und dem Wissen [mm] $\binom{n}{0} [/mm] = [mm] \binom{n}{n} [/mm] = 1$. Das geht wesentlich einfacher 
> (Denn
> prinzipiell ist für mich
> erstmal nur die zu zeigende Aussage äquivalent damit, zu
> zeigen, dass
> [mm]{k+n \choose k} \in \IN_0[/mm] (oder [mm]\IZ[/mm]) gilt... oder
> übersehe ich da
> etwas?)
Nein, du uebersiehst da nichts.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:13 Di 11.12.2012 | | Autor: | Marcel |
Hallo Felix,
> Moin Marcel,
>
> > P.S. Fred will wohl 'das Wissen' verwenden, dass
> > Binomialkoeffzienten der
> > genannten Form halt [mm]\in \IN_0[/mm] sind: Ist das denn
> bekannt?
> > Ansonsten
> > drehen wir uns ein wenig im Kreise - es sei denn, Du
> > kannst das auch
> > mit kombinatorischen Argumenten beweisen!
>
> ich wuerde es mit der Additionsformel fuer
> Binomialkoeffizienten beweisen und dem Wissen [mm]\binom{n}{0} = \binom{n}{n} = 1[/mm].
> Das geht wesentlich einfacher
achjoa, das Pascalsche Dreieck. Aber auch da braucht man ja wenigstens
dieses Wissen (oder muss diese Summenformel ${n [mm] \choose [/mm] k}+{n [mm] \choose [/mm] k+1}={n+1 [mm] \choose [/mm] k+1}$
selbst schnell beweisen!)
Was ich insgesamt eigentlich sagen will: Es wäre gut zu wissen, was der
Fragesteller so alles weiß...
> > (Denn
> > prinzipiell ist für mich
> > erstmal nur die zu zeigende Aussage äquivalent damit,
> zu
> > zeigen, dass
> > [mm]{k+n \choose k} \in \IN_0[/mm] (oder [mm]\IZ[/mm]) gilt... oder
> > übersehe ich da
> > etwas?)
>
> Nein, du uebersiehst da nichts.
Danke.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:39 Mi 12.12.2012 | | Autor: | anig |
Ok gut, aber könnt ihr mir bitte mal den Hintergrund erklären. warum beweise ich meine erste Frage wenn ich mit den Binomialkoeffizienten hantiere??? Ich verstehe das nicht so genau. Und wenn ich das so mache wie ihr gesagt habt, fehlt da nicht noch was?
|
|
|
| |
|
Hallo anig,
> Ok gut, aber könnt ihr mir bitte mal den Hintergrund
> erklären. warum beweise ich meine erste Frage wenn ich mit
> den Binomialkoeffizienten hantiere??? Ich verstehe das
> nicht so genau. Und wenn ich das so mache wie ihr gesagt
> habt, fehlt da nicht noch was?
Freds Weg funktioniert, weil alle (nicht verallgemeinerten) Binomialkoeffizienten ganzzahlig sind. Das ist allerdings dabei eine unverzichtbare Voraussetzung.
Insbesondere folgt doch [mm] \vektor{n\\k}*n!=\produkt_{j=1}^{n}(k+j)\;\;\gdw \;\;\blue{\vektor{n\\k}=\bruch{\produkt_{j=1}^{n}(k+j)}{n!}}
[/mm]
Die blaue Gleichung ist doch das, was zu zeigen war: im Zähler steht ein Produkt aus n aufeinanderfolgenden natürlichen Zahlen, im Nenner steht n!, und auf der linken Seite steht eine ganze Zahl. Also muss das Zählerprodukt durch n! teilbar sein.
Das ist ein vollkommen gültiger und vollständiger Beweisweg. Er "erklärt" nur nicht, warum diese Teilbarkeit besteht.
Mit meinem Ansatz würdest Du (mit mehr Mühe!) herausfinden, warum tatsächlich alle Teiler von n! auch Teiler von (k+n)! sind. Das ist alles andere als offensichtlich. Betrachte mal
[mm] \bruch{11*12*13*14*15*16*17}{1*2*3*4*5*6*7} [/mm] Das kannst Du natürlich leicht kürzen, aber warum?
Im Zähler sind drei Primzahlen >7. Die können sich nicht wegkürzen. Bleiben also noch vier Faktoren. Im Nenner stehen aber, wenn man die 1 mal nicht mitzählt, sechs Faktoren. Warum ist das kürzbar?
Antwort: weil in 7! der Primfaktor 2 viermal, die 3 zweimal, und die 5 und die 7 je einmal vorkommen. Und das tun sie auch in jeder beliebigen anderen Folge von 7 natürlichen Zahlen, mindestens.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:17 Mi 12.12.2012 | | Autor: | Marcel |
Hallo reverend,
kurze Nachfrage meinerseits:
> Mit meinem Ansatz würdest Du (mit mehr Mühe!)
> herausfinden, warum tatsächlich alle Teiler von n! auch
> Teiler von (k+n)! sind. Das ist alles andere als
> offensichtlich. Betrachte mal
>
> [mm]\bruch{11*12*13*14*15*16*17}{1*2*3*4*5*6*7}[/mm]
das $n! | [mm] (k+n)!\,$ [/mm] gilt, ist doch klar - damit sind alle Teiler von [mm] $n!\,$ [/mm] auch
Teiler von [mm] $(k+n)!\,.$ [/mm] Meintest Du vielleicht, dass alle Teiler von [mm] $n!\,$ [/mm] auch
Teiler des Produkts [mm] $(k+1)*...*(k+n)\,$ [/mm] seien?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:22 Mi 12.12.2012 | | Autor: | reverend |
Hallo Marcel,
> kurze Nachfrage meinerseits:
>
> > Mit meinem Ansatz würdest Du (mit mehr Mühe!)
> > herausfinden, warum tatsächlich alle Teiler von n! auch
> > Teiler von (k+n)! sind. Das ist alles andere als
> > offensichtlich. Betrachte mal
> >
> > [mm]\bruch{11*12*13*14*15*16*17}{1*2*3*4*5*6*7}[/mm]
>
> das [mm]n! | (k+n)!\,[/mm] gilt, ist doch klar - damit sind alle
> Teiler von [mm]n!\,[/mm] auch
> Teiler von [mm](k+n)!\,.[/mm] Meintest Du vielleicht, dass alle
> Teiler von [mm]n!\,[/mm] auch
> Teiler des Produkts [mm](k+1)*...*(k+n)\,[/mm] seien?
Ja klar, das meinte ich. Darum geht es ja in dieser Aufgabe - und ich habe unsauber formuliert bzw. sogar falsch.
Danke für den Hinweis!
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:30 Mi 12.12.2012 | | Autor: | Marcel |
Hallo anig,
> Ok gut, aber könnt ihr mir bitte mal den Hintergrund
> erklären. warum beweise ich meine erste Frage wenn ich mit
> den Binomialkoeffizienten hantiere??? Ich verstehe das
> nicht so genau. Und wenn ich das so mache wie ihr gesagt
> habt, fehlt da nicht noch was?
auf "das, was fehlen könnte" wollte ich hinweisen: Es ist hier noch zu
zeigen, falls das nicht bei Euch irgendwo bewiesen wurde:
$${n [mm] \choose [/mm] k} [mm] \in \IN_0$$
[/mm]
für alle $n,k [mm] \in \IN_0\,.$ [/mm] Ich hatte gesagt: Mit "Kombinatorik" kann man
sich das auch überlegen.
Der Vorschlag von Felix war: Naja, das geht doch induktiv:
Es ist ${n [mm] \choose [/mm] 0}={n [mm] \choose [/mm] n}=1 [mm] \in \IN_0$ [/mm] für alle $n [mm] \in \IN_0$ [/mm] und dann kann
man mittels ${n [mm] \choose [/mm] k}+{n [mm] \choose [/mm] k+1}={n+1 [mm] \choose [/mm] k+1}$ (das
kann man beweisen, aber das kennst Du normalerweise: siehe
![[]](/images/popup.gif) Pascalsches Dreieck (klick!)) die Behauptung folgern.
(Induktionsbeweis - wenn ich mir das gerade richtig im Kopf überlegt
habe, formuliert man dabei in günstiger Weise die Behauptung so: Für alle
$n [mm] \in \IN_0$ [/mm] gilt: Für alle $k [mm] \in \IN_0$ [/mm] mit $0 [mm] \le [/mm] k [mm] \le [/mm] n$ gilt ${n [mm] \choose [/mm] k} [mm] \in \IN_0\,.$)
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:48 Do 13.12.2012 | | Autor: | anig |
Danke, mir hat das sehr gut weiter geholfen.
|
|
|
|
