Question

Induction proofs. a. Prove by induction: n sum i^3 = [n^2][(n+1)^2]/4 i=1 Note: sum is intended to be the summation symbol, and ^ means what follows is an exponent b. Prove by induction: n^2 - n is even for any n >= 1 10 points 6) Given: T(1) = 2 T(N) = T(N-1) + 3, N>1 What would the value of T(10) be?

7) For the problem above, is there a formula I could use that could directly calculate T(N)?



8) Using induction, prove that your formula is correct.

Answer 1

a) n sum i^3 = n^2[(n+1)^2]/4

   Base case n = 1

   LHS:
      1 sum i^3 = 1

   RHS:
       1^2[(1+1)^2]/4 = 1

   Base case satisfied

   Now we assume for n = k it is true

   k sum i^3 = k^2[(k+1)^2]/4

   we will prove for n = k + 1

   (k+1) sum i^3 = (k+1)^2[(k+2)^2]/4
  
   Starting from LHS:

   for n = k+1 we have

    k^2[(k+1)^2]/4 + (k+1)^3

   = (k^2(k^2 + 2k + 1) + 4*(k^3 + 1 + 3k^2 + 3k))/4
   = (k^4 + 2k^3 + k^2 + 4k^3 + 4 + 12k^2 + 12k)/4
   = (k^4 + 6k^3 + 13k^2 + 12k + 4)/4

   RHS:
       (k^2 + 2k + 1)(k^2 + 4k + 4)/4
       (k^4 + 4k^3 + 4k^2 + 2k^3 + 8k^2 + 8k + k^2 + 4k + 4)/4
       (K^4 + 6k^3 + 13k^2 + 12k + 4)/4

   Hence proved

b) n^2 - n is even

   Base case n =1
  
   1 -1 = 0
   0 % 2 = 0

   Base case holds

   We assume for n = k

   k^2 - k is even

   we will prove for n = k+1

    (k+1)^2 - k-1 is even

   (k+1)^2 - k-1
   k^2 + 2k + 1 -k -1
   k^2 + k
   k^2 -k + 2k

   k^2-k is even and 2k is even. Sum of two even is even . Hence proved

----------------------------------------------------

   T(1) = 2
   T(N) = T(N-1) + 3

   We have the formula

   T(N) = ((N-1)*N)/2 +1 + 3(N-1)

   T(10) = (9 * 10)/2 + 2 = 47

   Base case N= 1

   T(1) = 0*1/2 +1 + 3*0 = 2
  
   Base case holds

   We assume for N= k
    T(k) = (k)*(k-1)/2 + 1 + 3(k-1)

   We will prove for N = k+1

    T(k+1) = (k+1) * (k)/2 + 1 + 3(k)

    T(k+1) = T(k) + 3 // As given in the question
           = (k + 1)*k/2 + 1 + 3(k-1) + 3
           = (k+1)*k/2 + 1 + 3k

    Hence Proved