Search 75,856 tutors
FIND TUTORS
Ask a question
0 0

mathematical induction

Tutors, please sign in to answer this question.

1 Answer

Let's first write down the first few decompositions to see the pattern:
14 = 2(3)+1(8)            21 = 7(3)
15 = 5(3)                     22 = 2(3)+2(8)
16 = 2(8)                     23 = 5(3)+1(8)
17 = 3(3)+1(8)            24 = 8(3)
18 = 6(3)                     25 = 3(3)+2(8)
19 = 1(3)+2(8)            26 = 6(3)+1(8)
20 = 4(3)+1(8)            27 = 9(3)
 
As you can see, each decomposition contains either no 8, one 8, or two 8s, depending on whether the number, or its predecessor, or its successor is divisible by 3. We should base the induction proof on this fact.
 
Th.: Every integer n≥14 can be decomposed as a sum of 3's and 8's.
 
Pf. (ind.):
1. The statement is true for n=14, since 14=2(3)+1(8).
2. Assume the statement is true for an arbitrary but fixed n=k+1 (k≥13). We need to show the statement is true for n=k+2.
 
There are 3 cases:
 
(i) (k-1) is divisible by 3. Then (k+2) is divisible by 3, and the statement is true.
(ii) k is divisible by 3, i.e., k=3m for some integer m≥4.
     Then k+2 = 3m+2 = 3(m-2)+8, and the statement is true.
(iii) (k+1) is divisible by 3, i.e., k+1=3m for some integer m≥5.
     Then k+2 = 3m+1 = 3(m-5)+2(8), and the statement is true.
 
By the principle of induction, the statement is true for all n≥14.