(a) We are given the following recursive algorithm. Algorithm 1 Square Algorithm 1: procedure SQUARE(n: positive integer) 2 if n = 1 then 3 return 1

This is a question from my Discrete Mathematics course. It asks to prove using INDUCTION.

(a) We are given the following recursive algorithm. Algorithm 1 Square Algorithm1: procedure SQUARE(n: positive integer)2 if n = 1 then3 return 14 else if n = 2 then5: return 46 else7 return 2SQUARE(n — 1) — SQUARE(n — 2) + 28: end procedure Let P(n) be the statement: SQUARE(n) = 72?. Prove that P(n) is true for all positive integer n.