Induksjonsbevis
Lagt inn: 02/04-2007 17:29
Man skal bevise
[tex]\sum_{k=i}^n {k \choose i} = {{n+1} \choose {i+1}}[/tex]
ved induksjon på n. Men her er det jo to variabler; både i og n! Vi kan kalle påstanden over for P(n,i). Vi kan vise at [tex]P(n,i) \Rightarrow P(n+1,i)[/tex]:
[tex]\sum_{k=i}^{n+1} {k \choose i} = \sum_{k=i}^{n} {k \choose i} + {{n+1} \choose i} = {{n+1} \choose {i+1}} + {{n+1} \choose i} = {{n+2} \choose {i+1}}[/tex]
Det er også greit å vise P(1,1) ved å sette inn. Men så må vi vise at P(n,i) stemmer for alle i, ikke bare for i = 1. Og hva gjør vi da?
[tex]\sum_{k=i}^n {k \choose i} = {{n+1} \choose {i+1}}[/tex]
ved induksjon på n. Men her er det jo to variabler; både i og n! Vi kan kalle påstanden over for P(n,i). Vi kan vise at [tex]P(n,i) \Rightarrow P(n+1,i)[/tex]:
[tex]\sum_{k=i}^{n+1} {k \choose i} = \sum_{k=i}^{n} {k \choose i} + {{n+1} \choose i} = {{n+1} \choose {i+1}} + {{n+1} \choose i} = {{n+2} \choose {i+1}}[/tex]
Det er også greit å vise P(1,1) ved å sette inn. Men så må vi vise at P(n,i) stemmer for alle i, ikke bare for i = 1. Og hva gjør vi da?