Matematyka dyskretna – dr Marcin Raniszewski, dr inż. Witold Staszewski

Matematyka Dyskretna – ćw. 3

Dowody indukcyjne 1

Twierdzenie o indukcji matematycznej,

silnia, dwumian Newtona, symbol Newtona, trójkąt Pascala

Udowodnienie tezy

dla (

) z wykorzystaniem twierdzenia o indukcji matematycznej:

Jeżeli:

1. Teza

jest prawdziwa dla (

);

2. Dla dowolnego

(

) prawdziwa jest implikacja:

;

to teza

jest prawdziwa dla każdego (

).

Silnia:

(„n silnia”) ( ) określamy następująco:

Dodatkowo określamy:

.

Zatem:

…

Zauważmy na przykład, że

, i ogólnie:

Symbol Newtona:

Dwumian Newtona:

Matematyka dyskretna – dr Marcin Raniszewski, dr inż. Witold Staszewski

Trójkąt Pascala:

Zadania 1 i 2 proszę rozwiązać z wykorzystaniem dowodu indukcyjnego.

Zad. 1. Udowodnij, że dla

:

(a)

(b)

(c)

(d)

(e)

Zad. 2. Udowodnij, że dla

:

(a)

(b)

(c)

(d)

(e)

(f)

(g)

Zad. 3. Udowodnij, że:

(a)

jest wielokrotnością 10

(b)

jest wielokrotnością 10

(c)

jest wielokrotnością 10