Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
1
Twierdzenie o indukcji dla tezy :
Jeżeli:
krok 1: teza jest prawdziwa dla ;
krok 2: dla dowolnego prawdziwa jest
implikacja: ;
to teza jest prawdziwa dla .
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
1
Twierdzenie o indukcji dla tezy :
Jeżeli:
krok 1: teza jest prawdziwa dla ;
krok 2: dla dowolnego prawdziwa jest
implikacja: ;
to teza jest prawdziwa dla .
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
2
Twierdzenie o indukcji dla tezy
:
Jeżeli:
krok 1: teza jest prawdziwa dla
;
krok 2: dla dowolnego
prawdziwa jest
implikacja: ;
to teza jest prawdziwa dla
.
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
3
Udowodnić indukcyjnie:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
4
Udowodnić indukcyjnie:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
5
Silnia:
,
gdzie: .
Dodatkowo określamy:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
6
Dla :
Dla :
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
7
Symbol Newtona:
gdzie: , .
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
8
1.
2.
3.
4.
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
9
5.
6.
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
10
Dwumian Newtona:
czyli:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
11
Dwumian Newtona (przypadek dla ):
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
12
Trójkąt Pascala:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
13
Udowodnić indukcyjnie:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
14
Udowodnić indukcyjnie:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
15
Udowodnić indukcyjnie:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
16
Udowodnić indukcyjnie:
Matematyka Dyskretna – wykład 3
dr Marcin Raniszewski
17
Udowodnić indukcyjnie: