Answer to Question #98931 in Discrete Mathematics for Dristanta Wagle

Question

Use strong induction to prove that every integer n > 5 can be written as n = 4x + 3y for
non-negative x, y ∈ Z.

Answer 1

I prove using strong induction that for any n>5 P(n): n=4x+3y holds.

Base cases:

n=6: P(6): 6=4*0+3*2, thus x=0 and y=2

n=7: P(7): 7=4*1+3*1, thus x=y=1

I took two base cases because we’ll need to go two steps backwards in the induction step (k-2).

Induction step:

We assume that P(6)  P(7) ……. P(k) is true for a positive integer k greater than or equal to 8.

We must prove that P(k+1) also holds.

Since k is greater than or equal to 8 => 5<k-2 < k, thus P(k-2) holds, so we can apply the induction hypothesis.

So, k-2=4x+3y => k+1=(k-2)+3=4x+3y+3=4x+3(y+1) which proves that k+1 has the same form.

We have proved that P(6)  P(7) ……. P(k-2) => P(k+1)

According to strong induction principle, the proof is now complete and P(n) holds for any n>5.