Practice Questions for Exam after break (proofs/induction)

Sequences, counting (including probability), logic and truth tables, algorithms, number theory, set theory, etc.

Practice Questions for Exam after break (proofs/induction)

Postby Zerrigan on Mon Mar 24, 2014 7:36 pm

Hey all, I have a test next week after Spring Break and would like some extra help with these problems in order to make sure I am prepared for the actual test!

1. Use a proof by cases to show that for all real numbers x and y, the absolute value of X+Y is less than or equal to the absolute value of X + the absolute value of Y.

For this I am thinking simply breaking into cases using X is + or -, and Y is + or -. That seems fairly simple. If X is - and Y is - the absolute value of X+Y is equal to the absolute value of X + the absolute value of X. The same applies for X and Y both being +. If one is + and the other -, the absolute value of X + Y is going to be less than the absolute value of X + the absolute value of Y. Am I missing anything here? Once I actually write out my proof I'll be sure to post it to make sure it makes sense.

2. Using problem 1, prove that for all real numbers A and B, the absolute value of A-B is greater than or equal to the absolute value of A - the absolute value of B.

Is this not essentially the exact same thing as 1?

3. Use a contradiction argument to show that for all positive real numbers X,Y, and Z, if X>Z and Y^2=XZ, then X>Y>Z. Hint: X>Y>Z is equivalent to saying X>Y and Y>Z.

Contradiction arguments use the general form of p and not q implies r and not r, correct? So for this problem it would be if X>Z and Y^2=XZ and X less than or equal to Y less than or equal to Z. Is this correct?

4. Prove that if D is an odd integer that divides both A+B and A-B, then D divides both A and B.

The definition of divides is that there A|B if there is some integer K we can multiply A by to get B, correct? So for this problem it would be if K_1D=A+B and K_2D=A-B then K_3D=A and K_4D=B correct? (The underscores represent subscripts).

5.Prove that N is odd if and only if N^2 is odd.

The definition of odd is that a number N can be represented by 2K_1+1 yes? So for an if and only if argument we prove if N is odd then N^2 is odd, then we prove the converse of if N^2 is odd, N is odd?

6. Prove that the sum of two odd numbers is even.

So I simply add (2K_1 +1)+(2K_2+1) and simply from there?

7. Prove by way on contradiction that for integers A,B, and C, if A^2+B^2=C^2, then at least one of A and B is even. Hint, use problem 5 and 6.

This seems pretty overwhelming but I'm sure it will be easier once I have a better grasp of 5 and 6.

8. Prove that for all real numbers X and Y, if Y^3+YX^2 less than or equal to X^3+XY^2, then Y less than or equal to X. Hint, use a proof by contrapositive.

Contrapositive proofs reverse and negate the implication right? So for this it would be if Y>X, then Y^3+YX^2>X^3+XY^2?

9. Prove that the square root of 3 is irrational.

A rational number can be expressed as A/B where A and B are both integers. I'm not sure how to start this as I don't know how to express an irrational number.

10. 7^n -2^n is divisible by 5 for all natural numbers n. Hint, add a clever form of zero when doing the inductive step.

I can set the base case up for this fairly easily but I have no idea what the clever form of zero is during the inductive step.

11. (1+1/2)^n greater than or equal to 1+n/2.

This is another induction problem but I don't know how to deal with the inequality. Are there any particular tips I should use for these that don't apply to equalities?

12.Suppose x+1/x is an integer. Prove that x^2+1/x^2,...x^n+1/x^n are all integers.

Another induction problem. Once I really get into it I imagine I'll come back with some questions but nothing seems terribly awful about it just looking at it.

13. Let P and Q be positive integers with Q>P. Prove that Q-P divides Q-1 if and only if Q-P divides P-1.

I don't even know what process to use on this one. I know the if and only if means I will be using the converse. But where do I even start?

14. A student claims to have shown that 2=1. Critique the student's proof by finding the error in their argument. Explain your reasoning below.

Proof: Let a=b be an integer. Then we have the following.
1. a=b
2. a^2=ab
3. a^2-b^2=ab-b^2
4. (a-b)(a+b)=b(a-b)
5. a+b=b
6. 2b=b
7. 2=1

Things start to look strange around step 4/5. However, I'm not sure what is wrong. Obviously 2 doesn't equal 1...but I don't see the error.

Thanks for anyone willing to help me out, I would like to do well on the test :)
Zerrigan
 
Posts: 4
Joined: Mon Mar 24, 2014 7:04 pm

Sponsor

Sponsor
 

Re: Practice Questions for Exam after break (proofs/inductio

Postby little_dragon on Tue Mar 25, 2014 1:41 pm

Proof: Let a=b be an integer. Then we have the following.
1. a=b
2. a^2=ab
3. a^2-b^2=ab-b^2
4. (a-b)(a+b)=b(a-b)
5. a+b=b
6. 2b=b
7. 2=1

Things start to look strange around step 4/5. However, I'm not sure what is wrong.

if a=b then a-b=0
cant div by 0!!!
:wave:
User avatar
little_dragon
 
Posts: 178
Joined: Mon Dec 08, 2008 5:18 pm

Re: Practice Questions for Exam after break (proofs/inductio

Postby Zerrigan on Tue Mar 25, 2014 5:58 pm

Yea I had someone else point that out to me and I feel pretty ridiculous for not seeing it! Thanks for the help :) If you or anyone else sees any other problems they have insights for I would love to receive extra help!
Zerrigan
 
Posts: 4
Joined: Mon Mar 24, 2014 7:04 pm

Re: Practice Questions for Exam after break (proofs/inductio

Postby buddy on Tue Mar 25, 2014 6:40 pm

Zerrigan wrote:3. Use a contradiction argument to show that for all positive real numbers X,Y, and Z, if X>Z and Y^2=XZ, then X>Y>Z. Hint: X>Y>Z is equivalent to saying X>Y and Y>Z.

Contradiction arguments use the general form of p and not q implies r and not r, correct? So for this problem it would be if X>Z and Y^2=XZ and X less than or equal to Y less than or equal to Z. Is this correct?

Yes.

Zerrigan wrote:4. Prove that if D is an odd integer that divides both A+B and A-B, then D divides both A and B.

The definition of divides is that there A|B if there is some integer K we can multiply A by to get B, correct? So for this problem it would be if K_1D=A+B and K_2D=A-B then K_3D=A and K_4D=B correct? (The underscores represent subscripts).

Yes. But subscripts are a pain so maybe like this:

D is odd so D=2n+1. D divides, so A+B=(2n+1)k and A-B=(2n+1)j. Then (A+B)+(A-B)=2A=(2n+1)(k+j) Since 2A is even and D=2n+1 is odd then k+j has to be even (to equal 2A) so k+j=2m. Then A=(2n+1)(m) and D divides A. Do something like that for D|B.

Zerrigan wrote:5.Prove that N is odd if and only if N^2 is odd.

The definition of odd is that a number N can be represented by 2K_1+1 yes? So for an if and only if argument we prove if N is odd then N^2 is odd, then we prove the converse of if N^2 is odd, N is odd?

"If and only if" means "prove in both directions". The one way is easy: N=2k+1 so N^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1 is odd. The other way says: N^2 is odd; prove N must be odd. Maybe do contradiction?

Zerrigan wrote:6. Prove that the sum of two odd numbers is even.

So I simply add (2K_1 +1)+(2K_2+1) and simply from there?

Yes, because you'll get something you can take 2 out of to show that it's even.

Zerrigan wrote:7. Prove by way on contradiction that for integers A,B, and C, if A^2+B^2=C^2, then at least one of A and B is even. Hint, use problem 5 and 6.

If C^2 is odd then C is odd (by 5). Then only one of A^2, B^2 is odd (by 6). Suppose A^2 is odd. Then A is odd (by 5), leaving B as even. Etc.

Zerrigan wrote:8. Prove that for all real numbers X and Y, if Y^3+YX^2 less than or equal to X^3+XY^2, then Y less than or equal to X. Hint, use a proof by contrapositive.

Contrapositive proofs reverse and negate the implication right? So for this it would be if Y>X, then Y^3+YX^2>X^3+XY^2?

Yes. This one looks nasty. I think you probably need to do something with cubes like x^2-x^2y+xy^2-y^3<0, x^2-3x^2y+3xy^2-y^3<-2x^2y+2xy^2, (x-y)^3<2xy(y-x), (x-y)^3>2xy(x-y), 0>(x-y)[(x-y)^2+2xy]=(x-y)[x^2-2xy+y^2+2xy]=(x-y)[x^2+y^2]. Tghere's only one way for that to be less than 0.

Zerrigan wrote:9. Prove that the square root of 3 is irrational.

A rational number can be expressed as A/B where A and B are both integers. I'm not sure how to start this as I don't know how to express an irrational number.

This works like the proof they showed you for sqrt[2] irrational. It's just a little longer.

Zerrigan wrote:10. 7^n -2^n is divisible by 5 for all natural numbers n. Hint, add a clever form of zero when doing the inductive step.

I can set the base case up for this fairly easily but I have no idea what the clever form of zero is during the inductive step.

Nobody comes up with this on their own. You have to see it first, before you'd ever think of it. It's probably something like: Let 7^k - 2^k = 5m. Then 7^(k+1) - 2^(k+1) = 7^(k+1) - 2*7^k + 2*7^k - 2^(k+1) = 7*7^k - 2*7^k + 2*7^k - 2*2^k = 7^k(7-2) + 2(7^k-2^k), etc. They show an example at the bottom of this page.

Zerrigan wrote:11. (1+1/2)^n greater than or equal to 1+n/2.

This is another induction problem but I don't know how to deal with the inequality. Are there any particular tips I should use for these that don't apply to equalities?

I don't think so. You try stuff and see if it goes anywhere, is all you can do.

Zerrigan wrote:13. Let P and Q be positive integers with Q>P. Prove that Q-P divides Q-1 if and only if Q-P divides P-1.

I don't even know what process to use on this one. I know the if and only if means I will be using the converse. But where do I even start?

Try doing stuff from the defs and see if it goes anywhere. If Q-P divides then (Q-P)k=Q-1. Add same stuff to both sides: (Q-P)k + (P-Q)= (Q-1)+(P-Q), Qk-Pk+P-Q=Q-1+P-Q, (Q-P)k-(Q-P)=P-1, (Q-P)(k-1)=P-1 so Q-P|P-1. (the adding to both sides is another trick)
buddy
 
Posts: 123
Joined: Sun Feb 22, 2009 10:05 pm

Re: Practice Questions for Exam after break (proofs/inductio

Postby Zerrigan on Wed Mar 26, 2014 2:30 pm

Thank you for the help! I'll let you know if something isn't making sense.

EDIT.

So here is what I have for 1-7.


1. By definition, the absolute value of a number k is as follows. |k|=k when k>=0 and |k|=-k when k<0.

Case 1. Let X and Y both be >=0. Thus, |X|=X and |Y|=Y. Since X+Y>=0, both |X|+|Y|>=0 and |X+Y|>=0. Therefore, |X|+|Y|=|X|+|Y| and |X|+|Y|<=|X+Y|.

Case 2. Let X and Y both be <=0. Thus, |X|=-X and |Y|=-Y. Hence, |X|+|Y|=-X-Y=-(X+Y). However, since the absolute value of a negative number is the opposite of the number, for X,Y<0, -(X+Y)=|X+Y|. Therefore, |X|+|Y|=-(X+Y)=|X+Y| and |X|+|Y|<=|X+Y|.

Case 3. Let X>=0 and Y<0. Thus, |X|=X and |Y|=-Y. Hence |X|+|Y|=X-Y. Not that |X+Y|=X+Y when X+Y>=0 and |X+Y|=-(X+Y) when X+Y<0. Since X>=0 and Y<0, X-Y>=X+Y and -X-Y=-(X+Y)>=-X+Y. Either way, |X+Y|<=|X|+|Y|.

Case 4. Let X<0 and Y>=0. Using case 3, |X|=-X and |Y|=Y. Hence |X|+|Y|=Y-X. Since X<0 and Y>=0, Y-X>=Y+X and -Y-X=-(Y+X)>=-Y+X. Either way, |X+Y|<=|X|+|Y|.


2. Using problem 1,

Case 1. Let |A|>=|B|. Also, let A=A-B+B. Thus, |A|=|A-B+B|. Using problem one, |A|=|A-B+B|<=|A-B|+|B|. Therefore, |A|-|B|<=|A-B|.

Case 2. Let |B|>=|A|. Also, let B+B-A+A. Thus, |B|=|B-A+A|. Using problem one, |B|=|B-A+A|<=|B-A|+|A|. Therefore, |B|-|A|<=|B-A|.


3. By contradiction,

Assume if X>Z and Y^2=XZ then X>Y>Z and X<=Y<=Z. Thus, we have Z>Y>X. Hence, Z>X. However, this contradicts the hypothesis of X>Z.

Is that really all there is to 3?


4. If D is odd then D=2N+1. Also, if D is even then D=2N. Note, if D|A+B then there is some integer K_1 we can multiply by D to get A+B. This means there is also some integer K_2 we can multiply by D to get A-B.

Knowing D=2N+1 and that D|A+B and D|A-B, we know that there are some integers K_1 and K_2 such that (A+B)=(2N+1)K_1 and (A-B)=(2N+1)K_2.

Note that (A+B)+(A-B)=2A, which by definition of even numbers, is even. Also, note that 2A=(2N+1)(K_1+K_2). Therefore, since 2A is even, (2N+1)(K_1+K_2) must be even. Hence, let K_1+K_2=2K_3. Thus, 2A=4NK_3+2K_3 and A=K_3(2N+1). Note that D=2N+1 so A=K_3(2N+1). Therefore, D|A.

Now, note that (A+B)-(A-B)=2B, which by definition of even numbers, is even. Also, note that 2B=(2N+1)(K_2-K_1). Therefore, since 2B is even, (2N+1)(K_2-K_1) must be even. Hence, let K_2-K_1=K_4. Thus, 2B=4NK_4+2K_4 and B=K_4(2N+1). Note that D=2N+1 so B=K_4(2N+1). Therefore, D|B.


5. If a number K is odd, then K=2J+1 for some integer J.

If N is odd, then N=2K_1+1 for some integer K_1. Thus, N^2=(2K_1+1)^2=4(K_1)^2+4K_1+1. Let 4(K_1)^2+4K_1=2K_2 for some integer K_3. Thus, N^2=2k_2+1. Therefore, if N is odd, N^2 is odd.

By contraposition, if N is even, then N=2K_3 for some integer K_3. Thus, N^2=(2K_3)^2=4(K_3)^2. Let 4(K_3)^2=2K_4 for some integer K_4. Hence, N^2=2k_4. Therefore, if N is even, N^2 is even, and by contraposition, if N^2 is odd, then N is odd.


6. Let X and Y both be odd integers. Thus, X=2K_1+1 and Y=2K_2+1 for some integer K_1 and K_2. Hence, X+Y=2K_1+1+2K_2+1=2K_1+2K_2+2=2(K_1+K_2+1) where K_1+K_2+1=K_3 for some integer K_3. Hence, X+Y=2K_3, which is even.


7. By contradiction, if A^2+B^2=C^2 and both A and B are odd, then by problem 5 if A^2 is odd, then A is odd and if B^2 is odd, then B is odd. Also, A^2+B^2=C^2 which is even by 6. By 5, if C^2 is even, then C is even. Hence, C=2K_1 and C^2=4(K_1)^2=4M for some integers K_1 and M.

Note that A^2+B^2=(2K_2+1)^2+(2K_3+1)^2 for some integers K_2 and K_3. Thus, A^2+B^2=4((K_2)^2+K_2+(K_3)^2+K_3)+2=C^2. Hence, C^2=4K_4+2 for some integer K_4=(K_2)^2+K_2+(K_3)^2+K_3. However, 4M doesn't equal 4K_4+2 for integers K_4 and M. Therefore, by contradiction, A or B must be even.

Thanks again for all the help!
Zerrigan
 
Posts: 4
Joined: Mon Mar 24, 2014 7:04 pm

Re: Practice Questions for Exam after break (proofs/inductio

Postby Zerrigan on Sat Mar 29, 2014 11:31 pm

Here is 9-12

9. By contradiction, assume rt3 is rational. Thus, rt3 can be expressed as A/B for integers A and B where B isn't 0 and A and B are in lowest terms. Thus 3=A^2/B^2 and A^2=3B^2. Thus, A^2 is divisible by 3. This means A is divisible by 3. Hence, A^2 is divisible by 9. Now, B^2=A^2/3 and B^2 is divisible by 3. This means both A and B are divisible by 3, so they weren't in lowest term which is a contradiction.


10. Let N=1. Thus, 7^1-2^1=5 which is divisible by 5.

Now, consider N+1. Thus, 7^(N+1)-2^(N+1)=7^(N+1)-(2)7^N+(2)7^N-2^(N+1)=7^N(7-2)+2(7^N-2^N)=7^N(5)+2(7^N-2^N). Now, 7^N(5) is divisible by 5 and 2(7^N-2^N) is divisible by 5 by induction. Thus, we can factor out a 5 and we have 7^n(5)+2(7^N-2^N)=7^(N+1)-2^(N+1) which must be divisible by 5.
Zerrigan
 
Posts: 4
Joined: Mon Mar 24, 2014 7:04 pm


Return to Discrete Math