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!
Has anyone done number 20 in sec 4.1 yet? I'm not sure how to get started...
T. Qu: Does anyone know how to do #50 in section 4.1?
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 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 #40?
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?
The course website is currently down, but I don't remember writing down number 40 as a homework problem.
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.
