HW 1: - Rhea

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

• • Second, observe that, due to our restrictions on n,

• • 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.

_______

I agree with the person above me, but to put it in more proof terms, we can prove the base case with n=1, and through "strong induction" we are assuming that for n values, there must be one int that divides another. Since that set of values is a subset of n+1 values, isn't it true that at the very least the values from the (n values) subset could be used to fulfill the condition for the n+1 set?

I'm not 100% on this, so if someone sees something wrong with my logic, please let me know!

_______

I agree with that. For any set of n+2 integers (the n+1 statement) there exists a subset, A, not containing the new values 2n+1 nor 2n+2. This subset could be picked to have the property such that it's largest element is less than twice its length minus one. That is given length m, where a_i < 2(m-1) for all a in A. Given that this is a subset of the original statement, m < n+1 and thus can assume to be true. So the original set contains at least one suitable subset that through "strong induction" can be assumed to be true, which proves the original set too.

I havent really solved this yet, but i did notice that the number of elements in the "pool" you can choose from is for the inductive case, 2k elements. the number of elements you are choosing is k+1. k+1 is more than half of the pool of 2k elements. from the example n = 4, from 8 elements you choose 5, where 5 > 8/2. i think you may be able to derive something from that fact. also for n = k+1, the pool is 2k+2, and you choose k+2 elements, > (2k+2)/2 = k+1. so the inductive case would hold.

i dont know if this helps, im kind of stuck too, but some thoughts.

I am a bit stuck too, but I was trying to think how you can pick the (n+1) numbers so that there is no one that divides another, and to "try" to do this would mean that you can only pick prime numbers. So with the n=4 example, you can pick 2,3,5,7, but there are no other primes and therefore the next number you pick will be divisible by, or divide something else. It works for all other n, but I'm not sure yet how to solve this by induction.

========================================================================================================================================================

Have you done #49?

Here is what I am thinking.

Even thought x and y are positive numbers, but x-1 and y-1 are may not positive numbers.

ex: x=1 is positive number but x-1 is not. so, x-1 and y-1 can't be inductive hypothesis.

I'm not sure it is right.

any idea?

    Yes, that sounds about right (for number 49 right above). That was the logic that I was using.

The course website is currently down, but I don't remember writing down number 40 as a homework problem.

No, 40 is not an assigned problem. The problems are: 4.1(6,8,20,32,49,50) and 7.5(6,12,20,28).

In response to the two questions above mine: 1. I agree with you on this, it's very similar to the example we did in last Thursday's (the incorrect proof "for any reall # a!=0, we have a^n = 1), and so I also think that taking x-1 and y-1 nulls the primary conditions therefore the rest of the proof. 2. I believe he meant number 49, not 40

In regards of the first question on this page about question 20 in sec 4.1. This is a straight forward question where you prove a base case. For this question the base case would be when n = 7. And you can prove the LHS and RHS of the equation by following the normal prove by induction steps and you should see the answer.

As for 50. I believe we will have to prove the base case first and assuming it holds. Then prove the statement for n+1 . Let A be any set of n+2 which none exceeds 2n+2. Clearly 2n+1 or 2n+2 is not in the set of A. This is where I am stuck at for now.

Has anyone finished problem #8 from 4.1, I know the basic process but when I try to solve it down I get stuck with an answer that does not equal to the P(n+1) step, any suggestions on what I am doing wrong?

__________________________________________________________________________________________________

for #8... if you're following similar to what we did in class where we took the P(n) and added the new p(n+1) term to each side then i would suggest making sure on the RHS you find a common denominator between the old term and new p(n+1)term.

does anyone have any hints for #28 in 7.5?

For number 28 in section 7.5, skim over sections 6.1 and 6.2 of the textbook for a quick overview of probability. In particular, pages 397 and 403 state that for events E1 and E2 in the sample space S, p(the union of E1 and E2) = p(E1) + p(E2) - p(the intersection of E1 and E2). Apply those concepts along with the ideas of the principle of inclusion-exclusion.

Also, you can get a lot of help from looking at the answers for the odd ones around 28. Like in number 27 you can see there are no intersections of more than 4 events because no more than 4 of the events can happen at the same time. This helped me solve 28.

Can anyone give me some tips on the proper way to do all the algebra that we need to do when there are factorials? I know that there are special ways to deal with logs and exponents and such, but what do you do with all the factorial stuff?

In regards to factorials, you can treat them as just multiplication: n! = n * (n - 1) * ... * 1. A fact useful for the homework is: n! * (n+1) = (n+1)!.

Thanks a lot that does help!

For problem 28 what you need to find is p(E1UE2U.....UEn), then you expand it by Inclusion and Exclusion rule, but notice in the problem it says no two events can take place at same time, that means the probability of intersection of events is 0, so the probability of the union of the event is just the sum of probabilities of each individual event. Hongshan

________________________________________________________________________________________________________________________________________________________
Is Section 7.5 supposed to be on inclusion and exclusion? If so I think my international version of the book does not match us right.

Thanks

Section 7.5 is on the inclusion-exclusion principle.

Vishal Gala

Does it matter if we give the proofs by induction or is it ok if we prove the problems by any other methods?

I am certain he will want the proofs for 4.1 to be done using induction. Since induction not only proves the problems for a particular value but, also any other value thats a part of the set in question it's a good idea to use induction.

I agree it is probably best to use induction, otherwise you may not get full credit.