Indukcja matematyczna dla dwóch liczb

[rapi2s]

Mam problem z następującym zadaniem:

Udowodnij, stosując metodę indukcji matematycznej, następujący fakt:
dla dowolnych liczb naturalnych \(\displaystyle{ a, b \ge 1}\) mamy \(\displaystyle{ a!b!|(a + b)!}\).
Wskazówka: zastosuj indukcję względem \(\displaystyle{ a + b}\).

Potrafię pokazać pierwszy krok indukcyjny (dla \(\displaystyle{ a=1, b=1}\)). Jednak nie umiem wyliczyć drugiego kroku. Zakładam, że dla pewnych \(\displaystyle{ a,b}\) zachodzi \(\displaystyle{ (a+b)!=k \cdot a! \cdot b!}\) i nijak nie mogę dojść do tego, że \(\displaystyle{ (a+b+1)!=l \cdot (a+1)! \cdot b!}\). Dochodzę tylko do tego, że \(\displaystyle{ (a+b+1)!=k \cdot (a+1)! \cdot b! + k\cdot b \cdot a! \cdot b!}\)

[AdamL]

\(\displaystyle{ (a+b+1)!=(a+b)! \cdot (a+b+1)}\)
\(\displaystyle{ (a+1)!=a! \cdot (a+1)}\).
\(\displaystyle{ (b+1)!=b! \cdot (b+1)}\).

[rapi2s]

AdamL własności, które napisałeś są dla mnie oczywiste, ale spójrz na to gdzie mam problem. Umiem to poprzekształcać tak:

\(\displaystyle{ (a+b+1)!=(a+b+1) \cdot (a+b)!=((a+1)+b) \cdot k\cdot a! \cdot b!=k\cdot(a+1)!\cdot b! + k \cdot b \cdot a! \cdot b!}\). Widać, że pierwszy składnik sumy dzieli się przez \(\displaystyle{ (a+1)! \cdot b!}\) ale nie jest dla mnie oczywiste, że drugi składnik też się przez to dzieli.

[Premislav]

Oto i jest drugi krok indukcyjny:

Założenie: dla pewnego \(\displaystyle{ n \in \NN, n \ge 2}\) i dowolnych \(\displaystyle{ a,b \in \NN^+}\), takich że \(\displaystyle{ a+b=n}\) zachodzi podzielność
\(\displaystyle{ a!b! |(a+b)!}\).

Teza: jeśli powyższe [założenie] jest prawdą, to i dla dowolnych \(\displaystyle{ a,b \in \NN^+}\) takich, że \(\displaystyle{ a+b=n+1}\) mamy
\(\displaystyle{ a!b!|(a+b)!}\)

Dowód: jeżeli \(\displaystyle{ a+b=n+1}\), to zarówno \(\displaystyle{ (a-1)+b=n}\), jak i \(\displaystyle{ a+(b-1)=n}\)
i z założenia indukcyjnego otrzymujemy następujące podzielności:
\(\displaystyle{ (a-1)!b! |(a+b-1)!\\ a!(b-1)!|(a+b-1)!}\)

Zatem \(\displaystyle{ (a+b)!=(a+b)\cdot k a!(b-1)!=(a+b)\cdot l(a-1)!b!}\) dla pewnych naturalnych \(\displaystyle{ k,l}\).
Jeżeli \(\displaystyle{ a|l}\) lub \(\displaystyle{ b|k}\), to sprawa załatwiona. Załóżmy zatem, że
\(\displaystyle{ a\nmid l \wedge b \nmid k}\)
Z równości \(\displaystyle{ (a+b)\cdot k a!(b-1)!=(a+b)\cdot l(a-1)!b!}\) (z założeń wynika, że te czynniki są niezerowe) otrzymujemy, że
\(\displaystyle{ ka=lb}\)
Skoro \(\displaystyle{ a\nmid l \wedge b \nmid k}\), to \(\displaystyle{ (a,b)=q>1}\). Wówczas \(\displaystyle{ q}\) dzieli liczbę \(\displaystyle{ a+b}\), bo dzieli składniki. Ponadto liczby \(\displaystyle{ \frac a q}\) i \(\displaystyle{ b}\) są względnie pierwsze, czyli z równości \(\displaystyle{ ka=lb}\) wynika, że \(\displaystyle{ \frac a q |l}\).
Zbierając to do kupy mamy istnienie takich \(\displaystyle{ k', l' \in \NN}\), że \(\displaystyle{ l=\frac a q \cdot l'}\)
oraz \(\displaystyle{ a+b=q \cdot k'}\), więc po wstawieniu tych syfów otrzymujemy
\(\displaystyle{ (a+b)!=(a+b)\cdot l(a-1)!b!=q k'\frac a q l'(a-1)!b!=(k'l')a!b!}\)
co kończy dowód.
Uff, na pewno da się prościej, ale niestety jestem "humanistą" (w tym pejoratywnym, potocznym znaczeniu).-- 5 lis 2016, o 20:19 --Aha, sorry, jednak jeżeli \(\displaystyle{ a=1}\) lub \(\displaystyle{ b=1}\), to moje rozumowanie się trochę psuje, ale wówczas teza zadania jest tak trywialna, że szkoda pisać.