23381

Często wystarczy udowodnić Lemat

Zał. T(k),k>n₀ Teza T(* + l)

Przykład.

Udowodnić nierówność Bernoulliego V/i€N (l+p )ⁿZ I + np. gdzie p > -1

Dowód indukcyjny.

I.    Nierówność jest prawdziwa dla n=l bo

I + p ^ l+p

II.    Zał. Zakładamy, że nierówność zachodzi dla n=k

(l+p )^l £ / + kp

Teza Wykażemy prawdziwość nierówności dla n=k+l

(l+p)¹'¹ H I + (k+l)p

Dowód

Przekształcamy nierówność z tezy lematu indukcyjnego

(l+p)^H,Z 1 + (k+l)p (l+p)^k (l+p) 2 / + kp + p (1+P )^ł (l+P) S (l+p) + kp (l+p)l (l+p)¹- lj S kp

Ostatnia nierówność jest prawdziwa, ponieważ (1 +p )^k - 1 2 kp na podstawie założenia indukcyjnego, stąd

(1+P)I (1+P )^l-1) £ (l+p)kp = kp+kpr 2 kp.

□

Definicje rekurencyjne

Np.

- definicja rekurencyjna silni:

{0 / = I

(n+ !)/=(«+!)• n /

=> n! = n • (/»— 1)

«eN,    '

2-1, neN

- definicja symbolu Y.:

'L^ai^:=a i j-l

A

'L^ai='L^ai^+a*.i

j-i j-i

dla /; € IN