Induction and recursion computer science
Budget: $10 – $30 USD
1. (a) Write the simple recursive program sumcube (i.e., sumcube(n) calls itself on (n-1)) to compute the sum of first n cubes, i.e, $\Sigma_{i=1}^n(i^3)$
(b) Write the simple recursive program sumi (i.e., sumi(n) calls itself on (n-1)) to compute the sum of first n numbers, i.e, $\Sigma_{i=1}^n(i)$
(b) prove using simple induction that sumcube(n) = [sumi(n)]^2.
i.e., prove $\forall n \in N. P(n)$ where $P(n) = sumcube(n) = [sumi(n)]^2$
Hint: both sides of the equation requires simplification using the programs you write - other than that, everything is direct.
2. (a) Write a simple recursive program prod_arr_s(A,n) that inputs an array and its size and returns the product of the elements in the array.
(b) Using the assumption that the elements in the array are non-negative, and simple induction, prove that the output of prod_arr_s(A,n) is non-negative.
3. (a) Write a course-of-value recursive program prod_arr_c(A,n) (i.e., prod_arr_c splits the array in half) that inputs an array and its size and returns the product of the elements in the array.
(b) Using the assumption that the elements in the array are non-negative, and strong induction, prove that the output of prod_arr_c(A,n) is non-negative.
4. (a) Write a course-of-value recursive program using repeated division binlen(n) that inputs n and finds the length of n's binary representation.
(b) Prove using strong induction that binlen(n) <= n
(b) Write the simple recursive program sumi (i.e., sumi(n) calls itself on (n-1)) to compute the sum of first n numbers, i.e, $\Sigma_{i=1}^n(i)$
(b) prove using simple induction that sumcube(n) = [sumi(n)]^2.
i.e., prove $\forall n \in N. P(n)$ where $P(n) = sumcube(n) = [sumi(n)]^2$
Hint: both sides of the equation requires simplification using the programs you write - other than that, everything is direct.
2. (a) Write a simple recursive program prod_arr_s(A,n) that inputs an array and its size and returns the product of the elements in the array.
(b) Using the assumption that the elements in the array are non-negative, and simple induction, prove that the output of prod_arr_s(A,n) is non-negative.
3. (a) Write a course-of-value recursive program prod_arr_c(A,n) (i.e., prod_arr_c splits the array in half) that inputs an array and its size and returns the product of the elements in the array.
(b) Using the assumption that the elements in the array are non-negative, and strong induction, prove that the output of prod_arr_c(A,n) is non-negative.
4. (a) Write a course-of-value recursive program using repeated division binlen(n) that inputs n and finds the length of n's binary representation.
(b) Prove using strong induction that binlen(n) <= n