PROSTE ;) KÓŁECZKO Z INDUKCJI (18.10.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. Wykaż, że \frac{1}{1·2} + \frac{1}{2·3} + … + \frac{1}{n(n+1)} = \frac{n}{n+1} dla każdego naturalnego n. 2.2. Udowodnij, że dla każdego n ∈ ℕ, liczba 11^{n+2} + 12^{2n+1} dzieli się przez 133. 2.3. Wykaż, że dowolny n-elementowy zbiór ma 2^{n} podzbiorów. 2.4. Ci _{}ag Fibonacciego (F_{n}) jest określony nast_{}epuj _{}aco: F_{1} = 1, F_{2} = 1, F_{n+2} = F_{n} + F_{n+1} .

Wykaż, że dla każdego naturalnego n:

• ∑ _{i=1}^{n} F_{i} = F_{n+2} − 1

• F_{n} · F_{n+2} − F_{n+1}^{2} = (−1)^{n+1}

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

• F_{2n} = F_{n} · F_{n−1} + F_{n} · F n + 1

2.5. Wykaż, że dowolne n kwadratów można poci _{}ać na skończon _{}a liczb_{}e kawałków tak, by z otrzymanych kawałków złożyć jeden kwadrat o polu równym sumie ich pól.

2.6. Udowodnij, że:

• ∑ _{i=1}^{n} i = \frac{n(n+1)}{2}

• ∑ _{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6}

• ∑ _{i=1}^{n} (2i − 1) = n^{2}

• ∑ _{i=1}^{n} i(i + 1) = \frac{n(n+1)(n+2)}{3}