AlexMu behöver inte mer hjälp
AlexMu 168
Postad: 10 okt 16:42 Redigerad: 10 okt 17:07

Bevisa en egenskap hos binomialkoefficienterna

Jobbar med kombinatorik just nu och råkade hitta detta faktum.

a+bb=n=0an+b-1b-1\displaystyle \binom{a+b}{b} = \sum_{n=0}^a{\binom{n+b-1}{b-1}} för a0a\geq 0, b1b \geq 1 och aa,bb \in \mathbb{Z}

Jag har försökt bevisa detta med induktion. Har inte hållt på med särskilt mycket bevis på egen hand förut men jag antar att man måste bevisa att påståendet stämmer både för aa och bb. För aa är det relativt lätt:

Basfall: a=0a=0, då blir det  n=00n+b-1b-1=b-1b-1=1=0+bb\displaystyle  \sum_{n=0}^0{\binom{n+b-1}{b-1}} = \binom{b-1}{b-1} = 1 = \binom{0+b}{b}

Anta att påståendet gäller för något cc, c0c\geq 0 och cc \in \mathbb{Z}
Då har vi c+bb=n=0cn+b-1b-1\displaystyle \binom{c+b}{b} = \sum_{n=0}^c{\binom{n+b-1}{b-1}}


Kolla nu på fallet c+1c+1
n=0c+1n+b-1b-1=c+bb-1+n=0cn+b-1b-1=c+bb-1+c+bb=c+b+1b+1\displaystyle \sum_{n=0}^{c+1}{\binom{n+b-1}{b-1}} = \binom{c+b}{b-1}+\sum_{n=0}^{c}{\binom{n+b-1}{b-1}} = \binom{c+b}{b-1} + \binom{c+b}{b} = \binom{c+b+1}{b+1} (från pascals formel för det sista)

och därmed är påståendet bevisat för aa

Men sedan om man ska göra det för bb går det inte lika bra. 

Basfallet blir b=1b=1 vilket blir  n=0an0=n=0a1=a+1=a+11\displaystyle \sum_{n=0}^a{\binom{n}{0}} = \sum_{n=0}^a{1} = a+1 = \binom{a+1}{1}

Anta att påståendet stämmer för något cc så att c1c \geq 1 och cc \in \mathbb{Z}

Alltså a+cc=n=0an+c-1c-1\displaystyle \binom{a+c}c = \sum_{n=0}^a{\binom{n+c-1}{c-1}}

Fallet c+1 blir då n=0an+cc\displaystyle \sum_{n=0}^a{\binom{n+c}{c}}
Här ser jag dock ingen framgång. Man kan få fram induktionsantagandet med hjälp av pascals formel, men då introduceras en ny term som jag inte heller såg någon enkel framgång med. Några ideer? Behöver man bevisa påstående både för aa och bb? Jag tänker att beviset för aa kanske medför att det gäller för alla bb, men är osäker. Har inte lärt mig induktionsbevis i skolan än

Gustor 293
Postad: 10 okt 17:23 Redigerad: 10 okt 17:30

Du kan låta a vara ett givet, fixt godtyckligt ickenegativt tal, och definiera P(a, b) = P(b) som påståendet du ska visa, som vi nu tänker på som att det bara beror på en parameter b. Därefter gör du vanlig induktion dvs. visar ett basfall, typ P(1), sedan P(k) => P(k+1). Då kan vi dra slutsatsen att P(b) gäller för alla b. Rent formellt har vi visat att ∀b:P(a, b).

Slutligen så eftersom a var ett godtyckligt tal så måste ∀b:P(a, b) gälla för alla a, vilket betyder att vi visat att ∀a∀b:P(a, b), vilket var det vi ville visa.

Det går förstås att byta ut a och b i detta resonemang.

I just detta fall tror jag dock att ett direkt algebraiskt bevis, eller kombinatoriskt, är lättare.

AlexMu 168
Postad: 11 okt 17:42
Gustor skrev:

Du kan låta a vara ett givet, fixt godtyckligt ickenegativt tal, och definiera P(a, b) = P(b) som påståendet du ska visa, som vi nu tänker på som att det bara beror på en parameter b. Därefter gör du vanlig induktion dvs. visar ett basfall, typ P(1), sedan P(k) => P(k+1). Då kan vi dra slutsatsen att P(b) gäller för alla b. Rent formellt har vi visat att ∀b:P(a, b).

Slutligen så eftersom a var ett godtyckligt tal så måste ∀b:P(a, b) gälla för alla a, vilket betyder att vi visat att ∀a∀b:P(a, b), vilket var det vi ville visa.

Det går förstås att byta ut a och b i detta resonemang.

I just detta fall tror jag dock att ett direkt algebraiskt bevis, eller kombinatoriskt, är lättare.

Ok, det var det jag misstänkte. Tack för svar!

Svara
Close