matematikk.net

Heihei!

Jeg er bedt om å bevise at Pascals trekant angitt ved tall og ved binomialkoeffisienter, respektivt, er en og samme trekant. I bevisføringen skal induksjon og Pascals regel ( C(n+1,i) = C(n,i-1) + C(n,i) ) nyttes. Noen som har lyst til å bidra med råd og vink til hvordan en slik bevisføring skal utføres, da jeg selv "går i sirkel" og hele tiden kommer fram til at det som skal bevises er en selvfølge.

Det er ikke nødvendigvis noe negativt i at det du skal bevise blir en selvfølge. Snarere tvert i mot.

Men dette var da en merkelig oppgave. Bevæpnet med Pascals regel er det jo nesten ingenting igjen å vise. Kan du ikke skrive en av idéene dine? Det gjør ikke noe om det er en der du "går i sirkel".

Bevisføring er så absolutt ikke min sterke side, men er ikke dette bare bevis av en ekvivalens?

Hvis du skal vise [tex]A \Leftrightarrow B[/tex] så
1) Antar at A er sann og viser
[tex]A \Rightarrow B[/tex]

2) Antar at B er sann og viser
[tex]B \Rightarrow A[/tex]

Siden de impliserer hverandre har du en ekvivalens.

Takker for råd - nå ble jeg motivert til å igjen sette meg ned for å ta en titt på oppgaven. Jeg kom fram til noe jeg håper kan være et gyldig resonnement. Har ikke særlig kjennskap til matematisk formalisme, så jeg vet ikke om det kan regnes som et bevis, men - here we go:

Vi skal altså vise at en trekant 1 (Pascals trekant ved naturlige tall) og trekant 2 (Pascals trekant ved binomialkoeffisienter) er en og samme trekant. At binomialkoeffisienter er naturlige tall er en kjensgjerning (vet jeg har sett bevis for dette et eller annet sted), altså er problemet nå redusert til å vise at to trekanter bestående av naturlige tall er en og samme trekant.

Trekant 1 er i sin helhet generert ved å ha to uendelige sidestykker med 1'ere, for så å benytte seg av regelen "et tall er summen av de to tallene som står på skrå rett ovenfor". Dersom vi kan vise at disse to reglene også er gjeldende for trekant 2, må de være en og samme trekant. I trekant 2 er alle endestykkene på formen C(n,0) eller C(n,n) <=> det naturlige tallet 1. Videre har vi Pascals regel - de tallene på skrått rett ovenfor C(n+1,i) må nødvendigvis være C(n,i-1) og C(n,i) (Hmm, er dette gyldig...?). Altså: trekant 1 = trekant 2.

Virker dette greit? Fant ingen bruk for induksjon, og er heller ikke helt sikker på overgangen der jeg forbeholder at skrått ovenstående for C(n+1,i) må være C(n,i-1) og C(n,i).

Det ser veldig bra ut. Du bruker induksjon implisitt (For å vise at trekantene er like på en vilkårlig posisjon, dvs. [tex]{n \choose i} = P(n, i)[/tex] hvor [tex]P(n,i)[/tex] er det i'te elementet på den n'te raden av Pascals trekant, trenger du at de er like på plassene over, og plassene over der, og så videre) , men jeg tror at dette er et tilfelle hvor å gjøre det eksplisitt bare vil gjøre argumentet mindre klart.

Og at posisjonene over [tex](n+1, i)[/tex] er [tex](n,i)[/tex] og [tex](n, i-1)[/tex] kan du lett lage et argument for. Jeg har litt lyst til å si det er åpenbart, men det er vel subjektivt. Husk at trekanten blir bredere for hvert nivå nedover, og tenk litt på hvordan [tex](n+1, i)[/tex] og [tex](n,i)[/tex] må stå i forhold til hverandre.

En oppfølgingsoppgave til deg: fullfør beviset ved å bevise Pascals regel, gjerne både rent algebraisk og med et kombinatorisk argument.

Til Bogfjellmo:

Takk for "kvalitetsstempling" Med litt ettertanke ser jeg bruken av induksjon i beviset. Jeg er helt fersk i bevisførings-gamet - da er det litt vanskelig å skilne mellom hva som er åpenbart og hva som faktisk trengs vises - noen ganger skal jo også åpenbare ting vises!