Diskussion:Niklas den yngres identitet
Om det allmänt anses att ett bevis för detta är önskvärt att inkludera:
Antag
[math]\sum_{k=0}^n {n \choose k} - \sum_{k=1}^{n-1} {n \choose k} = 2[/math]
Vi vill visa
[math]\sum_{k=0}^{n+1} {n+1 \choose k} - \sum_{k=1}^n {n+1 \choose k} = 2[/math]
Bevis:
[math]VL = {n+1 \choose 0} + \sum_{k=1}^{n+1} {n+1 \choose k} - \sum_{k=1}^n {n+1 \choose k}[/math]
Nu utnyttjar vi Pascals identitet [math]{n-1\choose k} + {n-1\choose k-1} = {n\choose k}[/math] och får
[math]{n+1 \choose 0} + \sum_{k=1}^{n+1} {n+1 \choose k} - \sum_{k=1}^n {n+1 \choose k} = {n+1 \choose 0} + \sum_{k=1}^{n+1} \left({n \choose k} + {n \choose k-1}\right) - \sum_{k=1}^n \left({n \choose k} + {n \choose k-1}\right) = {n+1 \choose 0} + \sum_{k=1}^{n+1} {n \choose k} + \sum_{k=0}^{n}{n \choose k} - \sum_{k=1}^n {n \choose k} - \sum_{k=0}^{n-1} {n \choose k} = {n+1 \choose 0} + \sum_{k=1}^{n+1} {n \choose k} - \sum_{k=1}^n {n \choose k} + \left(\sum_{k=0}^{n}{n \choose k} - \sum_{k=1}^{n-1} {n \choose k}\right) - {n \choose 0}[/math]
Enligt induktionsantagandet:
[math]{n+1 \choose 0} + \sum_{k=1}^{n+1} {n \choose k} - \sum_{k=1}^n {n \choose k} + \left(\sum_{k=0}^{n}{n \choose k} - \sum_{k=1}^{n-1} {n \choose k}\right) - {n \choose 0} = {n+1 \choose 0} + \sum_{k=1}^{n+1} {n \choose k} - \sum_{k=1}^n {n \choose k} + 2 - {n \choose 0} = {n+1 \choose 0} + {n \choose n+1} - {n \choose 0} + 2[/math]
Men
[math]{n+1 \choose 0} = 1[/math]
[math]{n \choose n+1} = 0[/math]
[math]{n \choose 0} = 1[/math]
så
[math]{n+1 \choose 0} + {n \choose n+1} - {n \choose 0} + 2 = 2[/math]
vilket skulle visas.
--Eric 9 oktober 2009 kl. 18.19 (UTC)
