Consider the following program, where a and n are positive integers.

Input: a, n x = a;

m = n; y = 1;

while (m > 1) {

if m is even x = x*x;

m = m/2;

else if m is odd y = x*y;

x = x*x;

m = (m-1)/2;

}

Output x*y

Let xi , yi , and mi denote the value of the variables x, y, and m at the start of the ith iteration. Using induction show the following

i an = x mi i yi

Your proof must use induction. Otherwise you will not receive any credit.

3. Consider the following program, where a and n are positive integers. Input: a, n x = a; m=n; y = 1; while (m >1) if m is even x*x; x = else if m is odd y x m x*y; x*x ; (m-1)/2; = = = Output x*y Let ri, yi, and mi denote the value of the variables x, y, and m at the start of the ith iteration Using induction show the following mi Your proof must use induction. Otherwise you will not receive any credit