Hint Use strong induction on n In the induction step treat t

Hint: Use strong induction on n. In the induction step, treat the cases \'n even\' and \'n odd\' separately.

Prove that every n 2^6*1, etc.......... Hint: Use strong induction on n. In the induction step, treat the cases \'n even\' and \'n odd\' separately. 2^0*17, ^64=2^4*5, ^17=2^2*9, 80= in N can be written as a product of an odd integer and nonnegative integer power of 2. For instance: 36=

Solution

Proof by induction on n:

\"Every n in N can be written as a product of an odd integer and non-negative integer power of 2.\"

Step 1: Base case

The proof is trivial for n = 1 as 1 in an odd integer.

Moreover, 1 can be written as 2^0 * 1 (= 1 * 1 = 1).

Thus, the result is true for n = 1.

Step 2: Inductive hypothesis

Assume that the result is true for k < n.

i.e., every k (< n) in N can be written as a product of an odd integer and non-negative integer power of 2.

Step 3: Induction step

Here, two cases arises.

Case (i): n is odd

The result is obvious as n can be written as 2^0 * n.

Case (ii): n is even

Let n = 2k, for some natural number k < n.

By induction hypothesis, k = 2^m * n, for some non-negative integer m and odd integer n.

n = 2k

= 2*2^m * n

= 2^(m+1) * n

which is in the form of product of non-negative integer power of 2 and odd integer.

Hence, this completes the induction proof.