Complete the following proof: Procedure power (a: nonzero real number, n: a nonn

Question

Complete the following proof:

Procedure power (a: nonzero real number, n: a nonnegative int)

If n = 0

            Then return (1)

Else return (a * power (a, n-1))

                                                //output is an

State P(n) the propositional function to be proved.

Is strong induction needed? Why?

State P(0).

Prove P(0) true. Number each step (based on the pseudocode) and justify your answer.

State the inductive hypothesis.

State P(K+1).

Prove P(K+1) is true, identifying the inductive hypothesis.

Concluding statement.

Explanation / Answer

Q1) State P(n) the propositional function to be proved = P(N) = aN, where a: nonzero real number, n: a nonnegative int

Q2) Yes Strong induction is required?

Ans - With simple induction you use "if p(k) is true then p(k+1) is true" while in strong induction you use "if p(i) is true for all i less than or equal to k then p(k+1) is true", where p(k) is some statement depending on the positive integer k. So in our case P(0) = 1 for all i <= k where k = 1 and i < = 1 (i.e. i = 0).

Q3) State P(0):- P(0) = a0.

Q3) Prove P(0) true. - P(0) means n = 0. Thus from the above function when n = 0 => Then it return 1. Thus P(0) holds true for all n = 0 .

Q4) State the inductive hypothesis:- if P(k) is true then P(k+1) is also true. Thus P(k) = ak and P(k+1) = ak+1 for a: nonzero real number and k >0

Q5) State P(K+1):- P(K+1) = ak+1 = a1 * P(k)

Q6) P(0) = a0 = 1, P(1) = a1 = a * P(0), P(2) = a2 = a *P(1), P(k+1) = a * P(k+1-1) = a * P(k) [Proved!!]

Please let me know in case of any clarifications required. Thanks!  

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.