Use Strong Induction to prove that every integer x 14 can be

Use Strong Induction to prove that every integer x 14 can be written as a sum of 3’s and / or 8’s.

Let, P(x) = 14, 15, 16, 17. .......

We have to prove that P(x) is sum of multiple of 3 and multiple of 8.

i.e. P(k+1) = 3a + 8b ......(where a and b are positive or non-negative integers.)

1. Basis Step :

P(14) = 3(2) + 8(1) = 6 + 8 = 14

P(15) = 3(5) + 8(0) = 15 + 0 = 15

P(16) = 3(0) + 8(2) = 0 + 16 = 16

P(17) = 3(3) + 8(1) = 9 + 8 =17

2. Induction Step :

By Inductive Hypothesis we assume for any value of k : 14<= m <= k,

P(k) = 3a + 8b.

We need to prove that P(k+1) = k + 1 = 3a + 8b

So, let us assume m = k - 2 which is less than k and greater than 14

then by above assumption we can say,

k - 2 = 3a + 8b

add 3on both sides

k - 2 + 3 = 3a + 8b +3

therefore, k + 1 = 3a + 3 +8b

k + 1 = 3(a + 1) + 8b

Hence. we prove that k+1 is also sum of multiple of 3 and multiple of 8

So, we can say, every integer x >= 14 can be written as sum of 3\'s and / or 8\'s.