1. Prove by induction, that for every natural number n the following formulas are valid:
   • 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) for a>1
   
   
2. Prove that for every natural number n such that n>0,
   • 2ⁿ > n
   • n ⁿ ≥ n!
   
   
3. Find:
   • a formula which defines number of diagonals in a convex polygon as a function of the number of its sides and prove its correctness by induction.
   • a formula which express maximum number of cross-points for any n lines on the plane (e.g. two different lines have at most one cross-point, three lines have at most three cross-points, etc.) and prove its correctness using mathematical induction.
   
   
4. Prove that for every natural number n the following equalities hold:
   
   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. Find solutions to the equations. Prove that they are correct.
   • T(1) = 0, T(n) = 2T(n/2) + n, for all n being the power of 2.
   • T(1) = c, T(n) = T(n-1) + n, for all n >1 and a constant c.


6. Prove by induction that the following algorithms solve given problems correctly.
   1. The algorithm calculating the scalar product of the two vectors X, Y of length n,
      {ilSk := 0; i := 1; while i<n+1 do ilSk := X(i)*Y(i) + ilSk; i := i+1 od }
   2. The algorithm of finding the greatest element in a given sequence of n elements.
      {max := a(1); i := 2; while i<n+1 do if max <a(i) then max := a(i) fi; i := i+1 od }


7. Use mathematical induction to prove that
   S_i=1ⁿ (i/(i+1)! = 1 -(1/(n+1)! for all n>0.


8. Prove by induction that
   1. 2ⁿ< n! for n>3
   2. 2ⁿ> n²
   3. n³< n! for n>5


9. Consider the following recurrence:
   T(1) = 1, T(n) = 2T(n-1) + 3 for n>1.
   
   (a) Find value of T(n) for n = 2, 3, 4, 5.
   (b) Solve the above recurrence exactly by finding the closed form expression for it.
   
   
10. Consider the following recurrence where a and b are real numbers and a>1 :
    T(1) = 1, T(n) = aT(n-1) + b for n>1.
    
    (a) Find T(n) for n = 2, 3, 4, 5?
    (b) Solve the above recurrence exactly by finding the closed form expression for it.

 

« previous section

next section »