KÓŁECZKO Z INDUKCJI (i erudycji) 07.11.06

1. TEORIA

1.1. (Zasada indukcji) Niech W b_{}edzie pewnym zdaniem logicznym. Jeśli W (1) oraz dla każdego n ∈ ℕ zachodzi

W (n) ⇒ W (n + 1), to W (n) dla każdego n ∈ ℕ.

1.2. (Zasada indukcji (2), równoważna z (1)) Niech W b_{}edzie pewnym zdaniem logicznym. Jeśli W (1) oraz dla każdego n ∈ ℕ zachodzi

W (1) ∧ W (2) ∧ … ∧ W (n) ⇒ W (n + 1), to W (n) dla każdego n ∈ ℕ.

2.ZADANKA

2.1. Wieże z Hanoi - Jak nie b_{}edziesz si_{}e uczyć, b_{}edziesz kopać rowy (albo przekładać 100 kr _{}ażków).

Mamy 3 pr_{}ety a na nich n kr _{}ażków, różnej wielkości poukładane od najwi_{}ekszego do najmniejszego. Na pocz _{}atku wszystkie kr _{}ażki s _{}a na jednym pr_{}ecie. Ruch polega na przełożeniu kr _{}azka na inny pr_{}et, ale nie wolno kłaść wi_{}ekszego kr _{}ażka na mniejszym. Ilu potrzeba ruchów, aby przenieść wszystkie kr _{}ażki na inny pr_{}et?

2.2. Problem Flawiusza - Myśl_{}e, wi_{}ec żyje. Rzymianie zdecydowali si_{}e na zbiorowe samobójstwo. W tym celu staj _{}a w kr_{}egu i zabijaj _{}a

co trzeci _{}a osob_{}e (aż zostanie jedna osoba). Gdzie powinien ustawić się Flawiusz, aby zostać przy życiu?

2.3. Pizza Pepperoni - Akcja Matexacja! Ile kawałków pizzy można uzyskać za pomoc _{}a n prostoliniowych ci_{}eć nożem? (Jaka jest

maksymalna liczba L(n) obszarów wyznaczonych przez n prostych na płaszczyźnie?

2.4. Zadanko o dużych liczbach - Wi_{}ekszy nie znaczy lepszy. Udowodnij, że istnieje N takie, że dla każego n > N:

• 2^{n} n^{2}

• 99^{n} n^{99}.

2.5. Zadanko o średnich wi_{}ekszych i mniejszych - Napisz długi wzorek, może nazw _{}a go Twoim nazwiskiem.

Udowodnij, że x_{1}x_{2}x_{3} ⋯ x_{n} (\frac{x_{1}+x+2+··· +x_{n}}{n} )^{n} (Nierówno¶ć Cauchy’ego)

2.6. Zadanko o poszukiwaniach sumy - Szukajcie, a znajdzicie... Znajdź sum_{}e (wzór zależny od n)

• 1^{3} + 2^{3} + 3^{3} + ⋯+ n^{3}.

• 1^{k} + 2^{k} + 3^{k} + ⋯+ n^{k}.

2.7. O tym, jak dodawać odejmuj _{}ac, pot_{}eguj _{}ac lub nic-nie-robi _{}ac - To dziwne - pomyślał Puchatek - powiedziałem �aj� wcale nie ajaj _{}ac...

Ci _{}ag Fibonacciego zdefiniowany jest nast_{}epuj _{}aco: a_{0} = 1, a_{1} = 1 oraz dla każdej liczby naturalnej n zachodzi: a_{n+1} = a_{n} + a_{n+1} . Udowodnij, że • a_{1} + a_{2} + ⋯+ a_{n} = a_{n+2} − 1

• a_{1} + a_{3} + ⋯+ a_{2n+1} = a_{2n+2}

• a_{2n+1} = a_{n}^{2} + a_{n+1}^{2}

2.8. O jawności - Jawność działania organów władzy państwowej czy organów samorz _{}adu terytorialnego stanowi kr_{}egosłup nowoczesnej demokracji.

Znajdź i udowodnij wzór jawny dla rekurencji

• Ci _{}agu Fibonacciego

• a_{0} = e, a_{1} = m, a_{n} = \frac{a_{n−1} +a_{n−2}}{2}