Induksjonsbevis

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

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?
Magnus
Guru
Guru
Innlegg: 2286
Registrert: 01/11-2004 23:26
Sted: Trondheim

Denne kan du fint løse uten induksjon da.. Bruk den veldig kjente identiteten:
[tex]{n\choose k} = {n-1\choose k} + {n-1\choose k-1}[/tex]

Men du har vel lyst til å løse den ved induksjon .. ?
sEirik
Guru
Guru
Innlegg: 1551
Registrert: 12/06-2006 21:30
Sted: Oslo

Hehe, fikk den til nå, på en litt annen måte:

Påstand [tex]P_n[/tex]: [tex]\forall i \in \{0\ ,\ ...\ ,\ n\}:\ \sum_{k=i}^n {k \choose i} = {{n+1} \choose i+1}[/tex]

Vi vil sjekke om [tex]P_1[/tex] stemmer:

[tex]\forall i \in {0\ ,\ 1}:\ \sum_{k=i}^1 {k \choose i} = {{n+1} \choose i+1}[/tex]

For i = 0: [tex]\sum_{k=0}^1 {k \choose 0} = {0 \choose 0} + {1 \choose 0} = 1 + 1 = 2[/tex]

[tex]{{1+1} \choose {0+1}} = {2 \choose 1} = 2[/tex]

Altså stemmer påstanden ved i = 0.

For i = 1: [tex]\sum_{k=1}^1 {k \choose 1} = {1 \choose 1} = 1[/tex]

[tex]{{n+1} \choose {i+1}} = 1[/tex], altså stemmer påstanden ved i = 1.

Vi ser at [tex]P_1[/tex] stemmer. Anta [tex]P_n[/tex]. For alle [tex]i \in \{0\ ,\ ...\ ,\ n\}[/tex] vet vi da:

[tex]X = \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+1} \choose {i+1}}[/tex]

Altså ser vi at [tex]P_{n+1}[/tex] også stemmer, men ikke nødvendigvis for [tex]i = n+1[/tex]. Dette må også vises:

[tex]\sum_{k=n+1}^{n+1} {k \choose {n+1}} = {{n+1} \choose {n+1}} = 1[/tex]

[tex]{{n+1 + 1} \choose {n+1+1}}= 1[/tex]

Altså ser vi at [tex]P_{n+1}[/tex] stemmer også for [tex]i = n+1[/tex], og beviset er ferdig.
Svar