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.

Answer 1

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?

Answer 2

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.

Answer 3

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)$.