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)