1. Udowodnij stosując zasadę indukcji matematycznej, że dla dowolnej liczby naturalnej n zachodzą następujące wzory:
   • 1² + 2² + 3² + ... + n² = (1/6)n(n+1)(2n+1)
   • 1³ + 2³ + 3³ + ... + n³ = [(1/2) n (n+1)]²
   • 1 + a¹ + a² + ... + aⁿ = (aⁿ⁺¹ - 1)/(a-1) dla a>1
   
   
   
2. Udowodnij, że dla dowolnego naturalnego n>0,
   • 2ⁿ > n
   • n ⁿ ≥ n!
   
   
   
3. Znajdź
   • wzór wyrażający zależność liczby przekątnych w wielokącie wypukłym od liczby jego boków i udowodnić prawdziwość tego wzoru korzystając z zasady indukcji.
   • wzór pozwalający wyznaczyć maksymalną liczbę punktów przecięcia n prostych na płaszczyźnie (np. 2 proste mają co najwyżej 1 punkt przecięcia, 3 proste mogą mieć aż 3 punkty przecięć, itd.) i udowodnić jego słuszność.
   
   
   
4. Udowodnij, że dla dowolnej liczby naturalnej n zachodzą wzory:
   
   
   1. Σ _i=1...n(2i-1) = n ²
   
   
   
   2. Σ _i=1...n(2i-1)² = (1/3)n(4n ²-1)
   
   
   
   3. Σ _i=1...n(2i-1) ³ = n ²(2n ²-1)
   
   
   
5. Rozwiąż równanie rekurencyjne
   • T(1) = 0, T(n) = 2T(n/2) + n dla wszystkich n będących potęgą dwójki.
   • T(1) = c, T(n) = T(n-1) + n dla wszystkich n >1 i pewnej stałej c.
   
   
   
6. Udowodnij przez indukcję, że następujące algorytmy są poprawne
   1. algorytm obliczania iloczynu skalarnego dwóch wektorów X, Y o długości n ,
      {ilSk :=0; i :=1; while i<n+1 do ilSk := X(i)*Y(i) + ilSk; i := i+1 od }
   2. algorytm znajdowania największego elementu w danym n elementowym ciągu a.
      {max := a(1); i := 2; while i<n+1 do if max <a(i) then max := a(i) fi; i := i+1 od }

« poprzedni punkt

następny punkt »