Question

Prove by induction that any integer greater than or equal to 18 can be written as a sum of multiples of 4 and 7.

I have a base case:
18 = 4(1) + 7(2). Thus 18 can be represented as a sum of multiples of 4 and 7.

*MULTIPLES MUST BE NONNEGATIVE INTEGERS*

But I am having trouble formulating an inductive step. Can someone help?

Answer 1

n > 18

n = 4(a) + 7(b)

n+1 = 4(a) + 7(b) + 1

Your task, then, is to show that 1 (one) can be expressed as a linear combination of 4 and 7.

n+1 = 4(a) + 7(b) + 7(3) - 4(5) = 4(a-5) + 7(b+3)

What do yo think of the negative multiple on 4? Did anyone specify that the multiples had to be positive?

Answer 2

It must be nonnegative for both 7 and 4

Answer 3

so 0 and greater is ok but no negatives

Answer 4

Well, you didn't say that! Nevertheless, the problem is the same.

Your task, then, is to show that 1 (one) can be expressed as a linear combination of 4 and 7.

Let's see what you get.

Answer 5

I don't know how to do it :/

Answer 6

You can't go a hunting? I found 7(3) + 4(-5) without very little difficulty. Are you saying you cannot find a multiple of 4 that is one (1) greater than a multiple of 7?

Have you considered 4(2) + 7(-1)

Answer 7

Neither multiple can be negative... but yes I see 4(2) is one greater than 7(1)

Answer 8

I'm sorry for not being more clear above

Answer 9

so in your notation, a and b must be greater than or equal to 0

Answer 10

Let's see how it works, using BOTH the +1 I just presented and the previous +1

We have two versions of 1 at our disposal.:

A) 4(2) + 7(-1)
B) 4(-5) + 7(3)

Start from 18

18 = 4(1) + 7(2)

We've only one 4, so we can't use B

Then

19 = 18 + 1 = 4(1) + 7(2) + A = 4(1) + 7(2) + 4(2) + 7(-1) = 4(1+2) + 7(2-1)
19 = 4(3) + 7(1)

We've still not five of those 4s, so we're still stuck with A

20 = 19 + 1 = 4(3) + 7(1) + A = 4(3) + 7(1) + 4(2) + 7(-1)
20 = 4(5) + 7(0)

Now, will you look at that! We ran out of 7s. I guess we can't use A, any more.

21 = 20 + 1 = 4(5) + 7(0) + B = 4(5) + 7(0) + 4(-5) + 7(3)
21 = 4(0) + 7(3)

How very convenient. Now we have more 7s.

The question we ask our self is why did we have to start with 18? Why would 17 not do?

Answer 11

My problem is actually a bit larger than this. but proving this portion will allow me to complete the problem

Answer 12

I am not understanding how you went about doing this...what exactly was discovered here? I don't see a pattern

Answer 13

The only necessary pattern is that one implies the other. I showed above, generally that it is easy enough allowing a negative factor. However, we must have non-negative factors. Thus, I demonstrated that we can proceed from one integer to the next,

18 ==> 19 using Pattern A (1 7 remaining)
19 ==> 20 using Pattern A (0 7 remaining)
20 ==> 21 using Pattern B (3 7 remaining)

The induction, then, implies that we can continue without the tedious demonstration

21 ==> 22 using Pattern A (2 7 remaining)
22 ==> 23 using Pattern A (1 7 remaining)
23 ==> 24 using Pattern A (0 7 remaining)
24 ==> 25 using Pattern B (3 7 remaining)

3 Pattern A will always supply five 4s.
1 Pattern B will always supply three 7s.

Answer 14

The full question is: a group of n>=1 people can be divided into teams each containing 4 or 7 people. what are all the possible values of n? use induction to prove your answer is correct.

Answer 15

So what I did was, I showed explicitly that 4,7,8,11,12,14,15, and 16 can be written as multiples of 4 and 7 (no pattern here).

Then I noticed that every number 18 and greater could be represented as multiples of 7 and 4. So now I'm trying to prove that final piece

Answer 16

You have done well in your exploration.

In order for my cyclical pattern to work, we need at least five 4s when we run out of 7s. 18 is the least value that meets that criterion.

Answer 17

What do you know of Generating Functions?

Multiply these: \((1+x^{4} + x^{8}+x^{12}+x^{16})(1+x^{7}+x^{14})\)

Then do it again: \((1+x^{4} + x^{8}+x^{12}+x^{16}+x^{20})(1+x^{7}+x^{14})\)

Then do it again: \((1+x^{4} + x^{8}+x^{12}+x^{16}+x^{20})(1+x^{7}+x^{14} +x^{21})\)

Look at those exponents. Isn't this the list you just produced?
Fascinating. I dare you to get an exponent of 17 out of that!

That's just a little sideline.

Your induction step might look like this:

In order for n to imply n+1, we must know something about n.

If n has three 7s, use pattern A and n+1 will have two 7s.
If n has two 7s, use pattern A and n+1 will have one 7.
If n has one 7, use pattern A and n+1 will have no 7.
If n has no 7, use pattern B and n+1 will have three 7s.

This is ALL the cases there are. We have proven the induction step by exhaustion!
Not the prettiest induction step I've ever seen, but it is sufficient.

Answer 18

Wow thanks so much :) I finally understand

Answer 19

Woo-hoo!!! Give it enough time and in usually sinks in. Play with those Generating Functions, one day.