Would anyone like to meet and work on this homework some? I'm struggling some with the concept of induction and how to do it properly. Drop an e-mail to rhossler@purdue.edu or comment on this. Thanks!
This was all really helpful! Thank you all for the hints!
Has anyone done number 20 in sec 4.1 yet? I'm not sure how to get started...
- This problem is vulnerable to the same approach as problems six and eight. Write down what P(n) states. Then, below it, write down what P(n+1) states. Your goal is to connect these two statements. Sometimes it's easier to work your way backward from P(n+1), and other times it's easier to work your way forward from P(n).
- Here are two specific hints: first, notice that
$ n!=\frac{(n+1)!}{(n+1)} $
- Second, observe that, due to our restrictions on n,
$ \frac{3}{n+1}<1 $
- This should be enough to transform P(n) into P(n+1). -David
T. Qu: Does anyone know how to do #50 in section 4.1?
- Problem number fifty: as someone else once said, I have discovered a truly marvelous proof of this, which this margin is too narrow to contain. Actually it's not marvelous at all, extremely long, probably taking up ten times the space it should. But it's done. I'll outline it here.
- Let's call sets described by P(n) "S(n)" and sets described by P(n+1) "S(n+1)". The first thing to notice is that S(n+1) has one more element than S(n), and two more values that its elements can take (namely the integers 2n+1 and 2n+2).
- If neither of these integers are present in S(n+1), then trivially some S(n) is a subset of S(n+1), therefore the required integers are present in S(n+1).
- If ONE of the "extra" integers is present, then we can take Q to be the set that is given by S(n+1) with this extra integer removed. Q, then, is governed by the inductive hypothesis, and because Q is a subset of S(n+1), there exist integers in S(n+1) which are kind enough to divide.
- If BOTH of the "extra" integers are present, then construct Q by REMOVING 2n+1 from S(n+1) and CHANGING 2n+2 by dividing it in half. Q will be governed by the inductive hypothesis. Showing that this implies that S(n+1) is also governed by it takes a lot of work. The entire process from beginning to end requires accounting for all kinds of exceptions and alternative cases. It took me five pages. I'm sure someone else has a better proof but that's how I did it. -David
@David: Your method sounds like it would work in most cases, but there's one particular case for which I think it might not work (unless this is one of those "exceptions and alternative cases" you mentioned). For n=2, consider this S(n+1):
{2 3 5 6}
Both 5 and 6 are "extra" integers (2n+1 and 2n+2), so to get Q, we remove 5, and change 6 into 3, yielding the set: {2 3 3}
Since sets can't have repetition, that set is equivalent to {2 3}. This is a set of only n integers, not n+1, and further, neither integer divides the other. Do you have a workaround for this case? (For what it's worth, this problem has me totally stumped...)
-Chris
- Chris, you're exactly right, this is one of the exceptions you have to account for. In this case, you let (2n+2) be an integer that doesn't exceed 2n, but wasn't in the original S(n+1). That such integers exist is guaranteed by the fact that the number of "allowed values" is equal to 2n, whereas the number of "values taken" is equal to n+1. 2n is greater than n+1 for all n>1, therefore there are always extra values that weren't used initially. In the case you mentioned, the six could be changed to a 1. I think I shored up all the holes in the argument, but as long as it is, I wouldn't be surprised if there's an error I missed and the proof totally fails. But this is the only thing I could come up with.
It is asking us to prove that for any number n (lets say 4) you can pick n+1 integers (5) that are either less than or equal to 2n (8) at least one of the chosen integers can divide one of the other chosen integers in the set.
So if n=4 then the integers that are available to choose from are less than or equal to 2n=8
1, 2, 3, 4, 5, 6, 7, 8
We then choose any 5 (n+1) of these integers and we will see that it is not possible to choose 5 without having at least one of the integers able to divide another.
This is not an answer to the problem. I am just trying to make it more clear what it is asking for anyone who found the statement of the problem confusing.
_
