Help with Induction problem?

Question

I'm not sure where to start on this induction problem.

Problem: A group of $n \geq 1$ people can be divided into teams, each containing either 4 or 7 people. What are all possible values of $n$? Use induction to prove that your answer is correct.

This problem is similar to one where we prove that for all $n \geq 8$, $n$ was made up of multiples of 5 and 3.

This is similar, but I haven't gotten far because I can't seem to decide on a base case. The question says that for $n \geq 1$, but a group of 1 person, or 2 or 3, can't be split up into multiples of 4 and 7. So I think that I need to find $n$ for which all numbers greater than $n$ are made up of multiples of 4 and 7.

For the 5's and 3's problem, the base case was 8, which is $5+3$, but that doesn't work for this, as 11 works, and 12 works but not 13. Again, I'm not sure where the base case is, so I don't know where to begin.

My induction hypothesis was the following: For all $n\geq 1$, $n$ is the sum of multiples of 4 and 7. That is, $4x + 7y = n$, where $x$ and $y$ are positive integers.

Hint: $17$ is not good; $18$, $19$, $20$ and $21$ are good. – André Nicolas Oct 13 '13 at 21:21 — André Nicolas, Oct 13 '13 at 21:21

score 5 · Answer 1 · answered Oct 13 '13 at 21:18

5

HINT: You actually want to allow $x$ and $y$ to be $0$ as well: you want the integers $n$ that can be written in the form $4x+7y$ for non-negative integers $x$ and $y$. In order to answer the question, you’re going to have to start with $n=1$ and manually try to write it in this form, then try $n=2$, and so on, until you get a certain number of successes in a row. Clearly the first success is going to be $n=4$, followed by $n=7$ and $n=8$. How many consecutive successes do you need in order to prove by induction that every positive integer from that point on is a success?

answered Oct 13 '13 at 21:18

Brian M. Scott

616,228

If we get 4 consecutive successes we can prove using strong induction by adding 4 to the n-3 th case. But how can we prove this using ordinary induction where only the nth case is assumed to be true? – Akash Karnatak Sep 30 '20 at 09:25
@AkashKarnatak: I very much doubt that you can. – Brian M. Scott Sep 30 '20 at 14:57

score 3 · Answer 2 · answered Oct 13 '13 at 21:29

As I understand it, your question is where to start in doing this induction problems. There are two parts to the problem. (1) What are all possible values of $n$? (2) Use induction to prove that your answer is correct. Do them in that order. First, figure out what values of $n$ are possible; only after you have done that do you start constructing a proof by induction. So where do you start in working part (1)? I suggest starting with $1$: is $1$ a possible value of $n$ or not? (It's not.) Next I would figure out whether $2$ is possible or not. I would keep doing this until the pattern becomes clear. (Pretty soon you will be getting nothing but yeses.)

Once you've done part (1), writing up the induction proof shouldn't be a problem; it will be like some other induction proof you've seen. If you have trouble with that, though, you can bring it up here as another question.

score 0 · Answer 3 · answered Oct 13 '13 at 21:23

You could induct on the number of teams. If you have one team, then you have either $4$ or $7$ people. Now, if we assume that every team with $k$ people can be realized as $4x+7y$, and we add one more team, this team will have either $4$ or $7$ people. We get two cases:

$1.$ If we add a team of four people, then the decomposition is $4(x+1)+7y$.

$2.$ If we add a team of seven people, then the decomposition is $4x+7(y+1)$.

Help with Induction problem?

3 Answers3