Dowód indukcyjny

[Mathhh]

\(\displaystyle{ {n \choose k} + {n \choose k + 1} = {n +1 \choose k + 1}}\)
Taki dowód za pomocą indukcji przeprowadzamy dla \(\displaystyle{ n}\) czy dla \(\displaystyle{ n}\) i \(\displaystyle{ k}\) ?

[Premislav]

Jakoś pod koniec kwietnia 2007 roku, gdy byłem w kościele, ksiądz zapowiedział, że odczyta list biskupów polskich. Wtem rozległ się zachrypnięty od alkoholu głos:
– A po co to czytać?
Pewien parafianin w szarej kurtce, autor tychże słów, wyszedł demonstracyjnie z budynku.

Ja zadam pokrewne pytanie: a po co to dowodzić indukcyjnie?

Ale jeśli już koniecznie chcesz, to proponuję ustalić \(\displaystyle{ k\in \NN}\) i przeprowadzać indukcję po \(\displaystyle{ n\ge k+1}\).

[szw1710]

Ładny dowód można podać w oparciu o wzór dwumianowy Newtona.

\(\displaystyle{ \binom{n}{k}}\) to współczynnik przy \(\displaystyle{ x^k}\) w rozwinięciu \(\displaystyle{ (1+x)^n.}\)

\(\displaystyle{ \binom{n}{k+1}}\) to współczynnik przy \(\displaystyle{ x^{k+1}}\) w rozwinięciu \(\displaystyle{ (1+x)^n.}\)

\(\displaystyle{ \binom{n+1}{k+1}}\) to współczynnik przy \(\displaystyle{ x^{k+1}}\) w rozwinięciu \(\displaystyle{ (1+x)^{n+1}=(1+x)^n(1+x).}\)

Ale

\(\displaystyle{ (1+x)^n(1+x)=\left(\dots+\binom{n}{k}x^k+\binom{n}{k+1}x^{k+1}+\dots\right)(1+x)}\)

Potęgę \(\displaystyle{ x^{k+1}}\) dostajemy tu z działania \(\displaystyle{ \binom{n}{k+1} x^{k+1}\cdot 1+\binom{n}{k}x^k\cdot x.}\) Dlatego właśnie zachodzi wspomniany wzór.

[a4karo]

A dla mnie dużo łądniejszy jest dowód kombinatoryczny: Przypuśćmy, że mamy \(\displaystyle{ n}\) kul czerwonych i jedną niebieską: na ile sposobów można z nich wybrać \(\displaystyle{ k+1}\) kul?


Możemy wybrać albo \(\displaystyle{ k+1}\) czerwonych (na \(\displaystyle{ \binom{n}{k+1}}\) albo \(\displaystyle{ k}\) czerwonych i jedną niebieską (na \(\displaystyle{ \binom{n}{k}}\) sposobów).

[Mathhh]

a4karo, Skąd taki pomysł ?

[a4karo]

Z kombinatorycznej interpretacji wzoru dwumiennego: \(\displaystyle{ \binom{n}{k}}\) to ilość sposobów na wybranie zbioru k-elementowego ze zbioru n-elementowego