Bevisföring

Visa att $C (n, 0) + C (n, 1) \cdot 2 + C (n, 2) \cdot 2^{2} + . . . . + C (n, n) \cdot 2^{n} = 3^{n}$ .

Kan någon hjälpa mig med den här uppgiften? Jag har ju förstått att man kan tänka sig att exempelvis har vi tre bokstäver A,B och C. Det går ju att skriva $3^{3}$ ord med tre bokstäver(högerledet) och för att förstå VL:et, vi kan säga hur många av orden innehåller bokstaven A? hur många av orden innehåller bokstäverna B och C?.....

Men finns det något generellt sätt att bevisa sambandet?

När man har en summa av en massa binomialkoefficienter kan detvara användbart att jämföra med binomialsatsen.

Att försöka hitta en kombinatorisk tolkning vore förstås också kul. Ord med bokstäver tror jag fungerar bra även om jag skulle köra på tal uttryckta i bas 3.

SeriousCephalopod skrev:
När man har en summa av en massa binomialkoefficienter kan detvara användbart att jämföra med binomialsatsen.
Att försöka hitta en kombinatorisk tolkning vore förstås också kul. Ord med bokstäver tror jag fungerar bra även om jag skulle köra på tal uttryckta i bas 3.

Men finns det något algebraiskt sätt att bevisa det?

Ja, som SeriousCephalopod skrev.

Du kan skriva summan såhär:

${n\choose 0}2^{0}1^{n}+{n\choose 1}2^{1}1^{n-1}+\cdots+{n\choose n}2^{n}1^{0}.$

En jämförelse med Binomialsatsen ger det sökta svaret omedelbart.

$(a+b)^{n} = {n\choose 0}a^{0}b^{n}+{n\choose 1}a^{1}b^{n-1}+\cdots+{n\choose n}a^{n}b^{0}.$

Den lösning Albiki presenterat är i praktiken den snabbaste men finns också kombinatoriska argument som kan användas för att bevisa den här typen av identiteter.

Jag tycker att din (marx) idé om att det kan ha något med strängar som byggs upp av symboler var väldigt bra. Så även fast du nu har en lösning kan du gärna fundera mer på om det finns fler. De koncepten som jag tror är användbara för det är:

${n \choose k}$ kan tolkas som antalet binära strängar av längd n med k ettor.

exempel: ${4 \choose 2}$ räknar upp antalet binära strängar av längd 4 med 2 ettor: 1100, 0110, 0011, 1010, 0101, 1001

Samtidigt är $2^n$ det totala antalet binära strängar av längd n

exempel: $2^4$ är antalet binära strängar av längd 4 med godtyckligt många ettor: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

Och $3^n$ är antalet trinära trängar av längd n.

exmpel: $3^4$ är antalet trinära strängar av längd 4. 0000, 0001, 0002, 0010, 0011, 0012, 0020, 0021, 0022, 0100, 0101, 0102, 0110, 0111, 0112, 0120, 0121, 0122, 0200, 0201, 0202, 0210, 0211, 0212, 0220, 0221, 0222, 1000, 1001, 1002, 1010, 1011, 1012, 1020, 1021, 1022, 1100, 1101, 1102, 1110, 1111, 1112, 1120, 1121, 1122, 1200, 1201, 1202, 1210, 1211, 1212, 1220, 1221, 1222, 2000, 2001, 2002, 2010, 2011, 2012, 2020, 2021, 2022, 2100, 2101, 2102, 2110, 2111, 2112, 2120, 2121, 2122, 2200, 2201, 2202, 2210, 2211, 2212, 2220, 2221, 2222

Man kan hålla på med ord ABC istället för siffror 012 men var enklare att generera.

Identiteten ovan kan alltså tolkas som någon slags relation mellan antalen av olika typer av binära och trinära strängar och borde gå att härleda utifrån något argument om relationen mellan dem.

Svara

Visa senaste svar