Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
14
ROZDZIAŁ1.
n!
k!
·
(n−k+1)!
n−k+1
+n!·
(n−k+1)!
1
·
k!
k
=
k!·(n−k+1)!
·[(n−k+1)+k]=
k!·(n−k+1)!
n!·[n+1]
=
k!·(n+1−k)!
(n+1)!
.
n!
Otrzymaliśmyrównośćztezyindukcyjnej.Namocyzasadyindukcjimateż
matycznejtezasformułowanawtymzadaniujestprawdziwa.I
1.1.2.(a)Wypisaćwszystkiepodzbioryzbioru{1,2,3}.
(b)Udowodnić,żekażdyzbiórnżelementowymadokładnie2npodzbiorów.
(c)Udowodnić,żekażdyzbiórnżelementowymadokładnie(
n
k)podzbiorów
kżelementowych,(dla0śkśn).
Rozwiązanie(a).Zbiór{1,2,3}maosiempodzbiorów)zbiórpusty∅,
{1},{2},{3},{2,3},{1,3},{1,2},{1,2,3}.
Dowód(b).(i)Zbiór0żelementowyjestzbiorempustym,którymadokładż
niejedenpodzbiór)∅,1=2o.
(ii)Założenieindukcyjne)każdyzbiórnżelementowyma2npodzbiorówdla
każdegon∈No.
Tezaindukcyjna)każdyzbiór(n+1)żelementowyma2n+1podzbiorów.
Wystarczywykazaćtezęindukcyjnądlazbioru{1,2,...,n,n+1}.Namocy
założeniaindukcyjnegomaon2npodzbiorówniezawierającychelementun+1
oraz2npodzbiorówzawierającychtenelement,2n+2n=2n+1.I
Dowód(c).(i)Zbiór0żelementowymajedenpodzbiór,1=(
o
o).
(ii)Założenieindukcyjne)każdyzbiórnżelementowymadokładnie(
n
k)podż
zbiorówkżelementowychdla0śkśn.
Tezaindukcyjna)każdyzbiórn+1żelementowymadokładnie(
n+1
k)podzbioż
rówkżelementowychdla0śkśn+1.
Zbiór{1,2,...,n,n+1}majedenpodzbiór0żelementowyijedenpodzbiór
(n+1)żelementowy,1=(
n+1
o)=(
n+1
n+1).Niechteraz1śkśn.Namocy
założeniaindukcyjnegozbiórtenma(
n
k)podzbiorówkżelementowychnie
zawierającychliczby(n+1)oraz(
k11)podzbiorówkżelementowychzawież
n
rającychtęliczbę,(
n
k)+(
k11)=(
n
n+1
k).I
1.1.3.UdowodnićwzórdwumiennyNewtona)
(x+y)n=
Σ
klo
n
(n
k)xkyn1k.
Dowód.Wielomian(x+y)njestsumąjednomianówxkyn1k.Naprzykład
