Indukcja matematyczna

Twierdzenie 1. (zasada indukcji matematycznej) Niech T (n) oznacza pewną tezę o liczbie
naturalnej n. Jeżeli dla pewnej liczby naturalnej n

0

1

◦

teza T (n

0

) jest prawdziwa,

2

◦

dla każdej liczby naturalnej n ­ n

0

z prawdziwości tezy T (n) wynika prawdziwość T (n+1),

to teza T (n) jest prawdziwa dla każdej liczby naturalnej n ­ n

0

.

Twierdzenie 2. (inna wersja zasady indukcji) Niech T (n) oznacza pewną tezę o liczbie natu-
ralnej n. Jeżeli dla pewnej liczby naturalnej n

0

1

◦

teza T (n

0

) jest prawdziwa,

2

◦

dla każdej liczby naturalnej n ­ n

0

z prawdziwości tezy T (k) dla wszystkich k ¬ n wynika

prawdziwość T (n + 1),

to teza T (n) jest prawdziwa dla każdej liczby naturalnej n ­ n

0

.

Zobaczmy, jak stosować zasadę indukcji matematycznej w dowodzeniu różnych tez o liczbach

naturalnych.

Przykład 1. Udowodnij, że dla dowolnej liczby naturalnej n zachodzi równość

1

1 · 2

+

1

2 · 3

+ . . . +

1

n(n + 1)

=

n

n + 1

.

Rozwiązanie. 1

◦

. Dla n = 1 suma po lewej stronie równości składa się tylko z jednego

składnika

1

2

, zatem teza T (1) jest prawdziwa.

2

◦

. Pokażemy, że jeśli prawdziwa jest równość T (n) (to jest założenie indukcyjne)

1

1 · 2

+

1

2 · 3

+ . . . +

1

n(n + 1)

=

n

n + 1

,

to zachodzi także T (n + 1) (to jest teza indukcyjna)

1

1 · 2

+

1

2 · 3

+ . . . +

1

(n + 1)(n + 2)

=

n + 1
n + 2

.

Rozpiszmy lewą stronę tezy indukcyjnej tak, by było widać, jak skorzystać z założenia. Mamy

1

1 · 2

+

1

2 · 3

+ . . . +

1

n(n + 1)

+

1

(n + 1)(n + 2)

zał.

=

n

n + 1

+

1

(n + 1)(n + 2)

=

=

n(n + 2)

(n + 1)(n + 2)

+

1

(n + 1)(n + 2)

=

(n + 1)

2

(n + 1)(n + 2)

=

n + 1
n + 2

.

Stąd na mocy zasady indukcji dana równość jest prawdziwa dla każdego n ∈ N.

Oznaczenia W dalszym ciągu stosować będziemy następujące oznaczenia

n

X

i=m

a

i

= a

m

+ a

m+1

+ . . . + a

n

,

n

Y

i=m

a

i

= a

m

· a

m+1

· . . . · a

n

,

gdzie m, n są liczbami całkowitymi, m < n, natomiast a

m

, a

m+1

, . . . , a

n

oznaczają dowolne liczby

rzeczywiste. Mamy zatem np.

3

X

i=−1

2

i

= 2

−1

+ 2

0

+ 2

1

+ 2

2

+ 2

3

,

5

X

i=1

1

i

=

1
1

+

1
2

+

1
3

+

1
4

+

1
5

,

n

X

i=1

2i − 1
3i + 2

=

2 · 1 − 1
3 · 1 + 2

+

2 · 2 − 1
3 · 2 + 2

+ . . . +

2n − 1
3n + 2

,

n

X

i=0

√

i + 1 =

√

1 +

√

2 + . . . +

√

n + 1,

2

Y

i=−2

i = (−2) · (−1) · 0 · 1 · 2,

n

Y

i=1

i

i + 1

=

1
2

·

2
3

· . . . ·

n

n + 1

.

Dowolną sumę w takiej skróconej formie możemy zapisać na wiele sposobów, np.

8

X

i=3

i

2

= 3

2

+ 4

2

+ . . . + 8

2

=

5

X

i=0

(i + 3)

2

.

Wykorzystamy teraz zasadę indukcji do uzasadnienia prawdziwości wzoru na (a + b)

n

dla

dowolnej liczby naturalnej n. Czytelnik zna z pewnością wzory skróconego mnożenia

(a + b)

2

= a

2

+ 2ab + b

2

,

(a + b)

3

= a

3

+ 3a

2

b + 3ab

2

+ b

3

,

które są szczególnymi przypadkami wzoru dwumianowego Newtona dla n = 2 i n = 3.

Przykład 2. (dwumian Newtona) Udowodnij, że dla dowolnego n ∈ N, zachodzi równość

(a + b)

n

=

n

X

k=0

n
k

!

a

n−k

b

k

,

gdzie

n
k

dla k = 0, . . . , n oznacza symbol Newtona,

n
k

=

n!

k!(n−k)!

.

Rozwiązanie. Przeprowadzimy indukcję względem n. Tezą T (n) jest równość

(a + b)

n

=

n

X

k=0

n
k

!

a

n−k

b

n

.

Sprawdzimy prawdziwość T (1). Mamy

1

X

k=0

n
k

!

a

n−k

b

k

=

1
0

!

a

1

b

0

+

1
1

!

a

0

b

1

= a + b,

więc teza dla n = 1 zachodzi.
Załóżmy teraz słuszność tezy T (n). Wtedy

(a + b)

n+1

= a(a + b)

n

+ b(a + b)

nzał.

= a

n

X

k=0

n
k

!

a

n−k

b

k

+ b

n

X

k=0

n

k

!

a

n−k

b

k

=

=

n

0

a

n+1

+

n

1

a

n

b

1

+ . . . +

n

i

a

n+1−i

b

i

+ . . . +

n
n

a

1

b

n

+

+

n

0

a

n

b

1

+ . . . +

n

i−1

a

n+1−i

b

i

+ . . . +

n

n−1

a

1

b

n

+

n
n

b

n+1

.

Dla i = 1, . . . , n obliczymy współczynniki stojące przy a

n+1−i

b

i

w powyższej sumie. Mamy

n

i

!

+

n

i − 1

!

=

n!

i!(n − i)!

+

n!

(i − 1)!(n − (i − 1))!

=

=

n!(n − i + 1)
i!(n − i + 1)!

+

n!i

i!(n − i + 1)!

=

n!(n + 1)

i!(n + 1 − i)!

=

n + 1

i

!

oraz

n

0

= 1 =

n+1

0

i

n
n

= 1 =

n+1
n+1

. Stąd możemy napisać

(a + b)

n+1

=

n+1

X

k=0

n + 1

k

!

a

n+1−k

b

k

,

więc teza T (n + 1) jest prawdziwa. Z zasady indukcji wynika słuszność tezy dla dowolnej liczby
naturalnej n.

Uwaga. Korzystając z udowodnionej powyżej równości

n

i

!

+

n

i − 1

!

=

n + 1

i

!

możemy zbudować tzw. trójkąt Pascala, złożony ze współczynników kolejnych rozwinięć dwu-
mianu Newtona

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

1

5

10

10

5

1

1

6

15

20

15

6

1

1

7

21

35

35

21

7

1

Każda liczba wewnątrz tego trójkąta jest sumą dwóch sąsiednich liczb z poprzedniego wiersza.
Wiersz i-ty zawiera współczynniki występujące we wzorze na (a + b)

i−1

.

Przykład 3. Udowodnij indukcyjnie, że dla n ­ 2 prawdziwa jest nierówność

n

Y

i=1

2i − 1

2i

>

1

2

√

n

.

Rozwiązanie. Sprawdzimy najpierw słuszność nierówności T (2). Jej lewa strona jest równa

2 · 1 − 1

2 · 1

·

2 · 2 − 1

2 · 2

=

1
2

·

3
4

=

3
8

= 0, 375,

czyli jest większa od

1

2

√

2

≈ 0, 353.

Założmy teraz, że

n

Y

i=1

2i − 1

2i

>

1

2

√

n

.

Pokażemy, że

n+1

Y

i=1

2i − 1

2i

>

1

2

√

n + 1

.

Rozpiszmy lewą stronę tezy. Mamy

n+1

Y

i=1

2i − 1

2i

=

n

Y

i=1

2i − 1

2i

!

·

2(n + 1) − 1

2(n + 1)

=

n

Y

i=1

2i − 1

2i

!

·

2n + 1

2(n + 1)

.

Ponieważ z założenia mamy

n

Y

i=1

2i − 1

2i

>

1

2

√

n

,

a ułamek

2n+1

2(n+1)

jest dla naturalnych n dodatni, możemy napisać

n

Y

i=1

2i − 1

2i

!

·

2n + 1

2(n + 1)

>

1

2

√

n

·

2n + 1

2(n + 1)

.

Pozostało nam do sprawdzenia, czy

1

2

√

n

·

2n + 1

2(n + 1)

­

1

2

√

n + 1

.

Mamy dla naturalnych n

1

2

√

n

·

2n + 1

2(n + 1)

=

2n + 1

4

√

n(n + 1)

=

√

4n

2

+ 4n + 1

4

√

n(n + 1)

=

=

2

q

n

2

+ n +

1

4

4

√

n(n + 1)

>

√

n

2

+ n

2

√

n(n + 1)

=

√

n

√

n + 1

2

√

n(n + 1)

=

1

2

√

n + 1

,

zatem dana nierównośc jest prawdziwa dla dowolnej liczby naturalnej n ­ 2.

Zadanie 1. Udowodnij, że następujące równości są prawdziwe dla dowolnej liczby naturalnej n:

a) 1 + 2 + . . . + n =

n(n+1)

2

,

b) 1

2

+ 2

2

+ . . . + n

2

=

1

6

n(n + 1)(2n + 1),

c) 1

3

+ 2

3

+ . . . + n

3

=

n

2

(1+n)

2

4

,

d)

1

1·4

+

1

4·7

+ . . . +

1

(3n−2)(3n+1)

=

n

3n+1

,

e) 1 + 5 + 9 + . . . + (4n − 3) = n(2n − 1),

f) 1 · 1! + 2 · 2! + . . . + n · n! = (n + 1)! − 1,

g) suma pierwszych n nieparzystych liczb naturalnych jest równa n

2

,

h)

P

n

i=1

1

n+i

=

P

2n

i=1

(−1)

i+1 1

i

,

i)

P

n

i=1

i · (2

i

− 1) = (n − 1) · 2

n+1

+ 2 −

n(n+1)

2

,

j)

P

n

i=0

a

i

=

a

n+1

−1

a−1

dla dowolnego n ∈ N, gdzie a jest liczbą rzeczywistą 6= 1.

Zadanie 2. Udowodnij indukcyjnie nierówności (n ∈ N):

a) n! > 2

n

dla n > 3,

b) (1 + a)

n

­ 1 + na dla a > −1 (nierówność Bernoulliego),

c)

1

√

1

+

1

√

2

+ . . . +

1

√

n

­

√

n,

d)

1

1

2

+

1

2

2

+ . . . +

1

n

2

¬ 2 −

1

n

,

e)

P

n

i=1

1

n+i

>

13

24

dla n > 1,

f) 2

n+1

> 5n dla n ­ 3,

g) 3

n

­ 2n + 1.

Zadanie 3. Udowodnij, że dla dowolnej liczby naturalnej n:

a) liczba n

3

+ 2n jest podzielna przez 3,

b) liczba n

3

− n jest podzielna przez 6,

c) liczba 2

4n+1

+ 3 jest podzielna przez 5,

d) liczba 3

4n+2

+ 1 jest podzielna przez 10,

e) liczba n

7

− n jest podzielna przez 42,

f) liczba 4

n

+ 5 jest podzielna przez 3,

g) liczba 3

4n+3

+ 5

4n+1

jest podzielna przez 8.

Zadanie 4. Niech a

1

= a

2

= 1 oraz a

n+1

= a

n

+ a

n−1

dla n = 2, 3, 4, . . .. Zdefiniowany w ten

sposób ciąg 1, 1, 2, 3, 5, 8, 13, 21, . . . to ciąg Fibonacciego. Udowodnij indukcyjnie wzór na n-ty
wyraz tego ciągu

a

n

=

1

√

5

"

1 +

√

5

2

!

n

−

1 −

√

5

2

!

n

#

.

Zadanie 5. Udowodnij, że dla każdego n ∈ N liczba (2 +

√

3)

n

+ (2 −

√

3)

n

jest liczbą naturalną.

Zadanie 6. Udowodnij indukcyjnie, że dla każdej liczby naturalnej n i k = 0, . . . , n liczba
wszystkich k-elementowych podzbiorów zbioru n-elementowego wynosi

n
k

.

Zadanie 7. Udowodnij, że n różnych prostych na płaszczyźnie przecinających się w ustalonym
punkcie P dzieli płaszczyznę na 2n części.

Zadanie 8. Udowodnij, że suma miar kątów wewnętrznych dowolnego n-kata wypukłego wynosi
(n − 2)π.