Bizonyítsuk be, hogy a Pascal-háromszög n-edik sorában lévő számok összege 2^n?

[link]

Van bizonyítás is.

a=1, b=1 esetén következik a fenti állítás.

Persze azt is kell tudni, hogy a Pascal-háromszög n-enik sorának k-adik eleme (értelemszerűen 0<=k<=n, k;n€N) (n alatt a k).

De gondolati úton is meg lehet oldani; látjuk, hogy n=0-ra 2^0=1, az első sorban 1 darab 1-es van, tehát erre igaz.

Tegyük fel, hogy az állítás n-ig igaz. Nézzük, hogy az n+1-edig sorban mi lesz a helyzet: tegyük fel, hogy az n-edik sor tagjai:

a(0); a(1); a(2); ...; a(n-2); a(n-1); a(n)

(A zárójel alsó indexet jelöl.)

Tudjuk viszont azt is, hogy a két szélső elem 1:

1; a(1); a(2); ...; a(n-2); a(n-1); 1

Ezeknek az összegéről tudjuk, hogy 2^n-nel egyenlő.

Nézzük a következő sor tagképzését:

b(0)=1

b(1)=1+a(1)

b(2)=a(1)+a(2)

.

.

.

b(n-1)=a(n-2)+a(n-1)

b(n)=a(n-1)+1

b(n+1)=1

Ezeket az egyenleteket összeadjuk, akkor a

bal oldal: b(0)+b(1)+b(2)+...+b(n-1)+b(n)+b(n+1)

jobb oldal: 1+1+a(1)+a(1)+a(2)+[a(2)]+...+[a(n-2)]+a(n-2)+a(n-1)+a(n-1)+1+1

Két helyen szögletes zárójelet használtam, ezek a tagok a szemléltetés miatt kellenek, mivel a fenti összeadásból csak 1-1 lenne belőlük.

Látható, hogy az előző sor minden tagja ezzel az eljárással 2-szer lett összeadva. Az összeadás kommutativitására és asszociativitására hivatkozva az összeget át tudjuk írni

2*(1+a(1)+a(2)+...+a(n-2)+a(n-1)+1) alakra. A zárójelen belüli összegről tudjuk az indukciós feltevés miatt, hogy 2^n-nel egyenlő, tehát az összeg megegyezik 2*2^n-nel, ez pedig a hatványozás azonosságaiból kifolyólag 2^(n+1)-nel egyenlő. Mit az Isten, pont ez kellett nekünk.