Užití rekurentní formule pro binomické koeficienty k dokazování kombinatorických identit
Naším úkolem je dokázat, že pro každé nezáporné celé číslo n platí rovnost
± (2"; *). 2» = 2».
Postupujeme indukcí vzhledem k hodnotě n. Pro n = 0 tvrzení platí. Předpokládejme dále, že tvrzení platí pro nějaké nezáporné celé číslo n, a dokažme, že pak toto tvrzení platí také pro číslo n + 1. Označme nejprve
" '2n-k
2J
k=Q
)2n
Pak podle našeho předpokladu pro dané číslo n platí Qn = 2Zn. K uskutečnění indukčního kroku potřebujeme vypočítat hodnotu Qn+i- Přepišme nejprve poněkud naše vyjádření hodnoty Qn. Položme £ = n — k. Pak můžeme psát
n     / x n ,
i 2e'
Takže dostávame vyjadrení
£=0
Podobně obdržíme též vyjadrení
A7+1
n     , .
n + í
i   ) 2t
1 /
o_n \
Odtud dostávame
n+l
n + í + l
t      ) 2*'
Qn+Í = i + Yl
2n+i ' i      ) 2e
s využitím rekurentní formule pro binomické koeficienty. Dalšími úpravami tohoto posledního vyjadrení pak obdržíme
poněvadž
n + í
A7 + í
2^ l   ^   J • 2^+1 +1 + 2^ v ^ y 2^
n n+1
•E
n + £+l\    1     /2n + 2\ 1
2  ^ V     ^      7   2ť       n+1 2"+2
^Wn + A   1     /2n + l 1 + £ +       i "
£   )   2e    V n + 1 y 2"+1 n + A 1
2n + 2\     1 (2" + 2)
n + iy   2"+2     (n + 1)!-(n + 1)! 2"+2
(2n + l)!       1 /2n+l
(n + 1)! • n!   2"+1     \ " + 1 /   2"+1'
To ale znamená, že platí rovnost
111
odkud vychází
1 1
Qn+l = — • Qn
2n+2    ^"^J- 2n
takže
Qn+l =4(?n.
Protože podle indukčního předpokladu máme Qn = 22", dostáváme odtud
Q„+1 = 4-22" = 22"+2,
což bylo třeba dokázat.