6 a. Show by induction on n that 12 +22 +32 +...+n = n(n+1)(2n+1) b. Let...

   

Transcribed Image Text:

6 a. Show by induction on n that 12 +22 +32 +...+n = n(n+1)(2n+1) b. Let T(n) be defined recursively as follows: T(1) = c, and T(n) = 5T (#)+c vn5 C. where c is an arbitrary constant, and n = 5k for some non-negative integer k. Prove by induction on k that T(n) =n I +cn, for all Let T(n) be defined recursively as follows: 7(1) = c, and T(n) = 2T ()- integers n 2, where c is an arbitrary positive constant and [x] for any number x is the floor value of x. Prove by induction on n that T(n) cn logn + cn for all integers n 1. d. Let T(n) be defined recursively as follows: 7(1) = c, and T(n) = 4T (#) + n. Use the Master Theorem to find the O value of T(n). 6 a. Show by induction on n that 12 +22 +32 +...+n = n(n+1)(2n+1) b. Let T(n) be defined recursively as follows: T(1) = c, and T(n) = 5T (#)+c vn5 C. where c is an arbitrary constant, and n = 5k for some non-negative integer k. Prove by induction on k that T(n) =n I +cn, for all Let T(n) be defined recursively as follows: 7(1) = c, and T(n) = 2T ()- integers n 2, where c is an arbitrary positive constant and [x] for any number x is the floor value of x. Prove by induction on n that T(n) cn logn + cn for all integers n 1. d. Let T(n) be defined recursively as follows: 7(1) = c, and T(n) = 4T (#) + n. Use the Master Theorem to find the O value of T(n).