Zu zeigen
∑ (k = 0 bis n) (m + k über k) = (m + n + 1 über n)
Induktionsanfang: n = 0
∑ (k = 0 bis 0) (m + k über k) = (m + 0 + 1 über 0)
(m + 0 über 0) = (m + 0 + 1 über 0)
1 = 1
stimmt!
Induktionsschritt: n --> n + 1
∑ (k = 0 bis n + 1) (m + k über k) = (m + (n + 1) + 1 über (n + 1))
∑ (k = 0 bis n) (m + k über k) + (m + (n + 1) über (n + 1)) = (m + n + 2 über n + 1)
(m + n + 1 über n) + (m + n + 1 über n + 1) = (m + n + 2 über n + 1)
(m + n + 1)!/(n!·(m + 1)!) + (m + n + 1)!/((n + 1)!·m!) = (m + n + 2)!/((n + 1)!·(m + 1)!)
(m + n + 1)!·(n + 1)/((n + 1)!·(m + 1)!) + (m + n + 1)!·(m + 1)/((n + 1)!·(m + 1)!) = (m + n + 2)!/((n + 1)!·(m + 1)!)
(m + n + 1)!·(n + 1) + (m + n + 1)!·(m + 1) = (m + n + 2)!
(m + n + 1)!·((n + 1) + (m + 1)) = (m + n + 2)!
(m + n + 1)!·(n + m + 2) = (m + n + 2)!
(m + n + 2)! = (m + n + 2)!