1
$\begingroup$

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.

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

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.