Question

In: Advanced Math

3. To begin a proof by contradiction for “If n is even then n+1 is odd,”...

3. To begin a proof by contradiction for “If n is even then n+1 is odd,” what would you “assume true?

4. Prove that the following is not true by finding a counterexample.

“The sum of any 3 consecutive integers is even"

5. Show a Proof by exhaustion for the following: For n = 2, 4, 6, n²-1 is odd

6. Show an informal Direct Proof for “The sum of 2 even integers is even.”

Recursive Definitions

7. The Fibonacci Sequence is defined as follows:

F(1) = 1

F(2) = 1

F(n) = F(n-1) + F(n-2) for n>2.

The first 10 numbers in the sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55.

Find F(13) = ______________ and F(14) =______________

8. Prove the following property of the Fibonacci numbers directly from the definition.

F(n+3) = 2F(n+1) + F(n-3)+ 2F(n-2)

9. Find the 3^rd, 4^th and 5^th values in the sequence.

D(1) = 0

D(n) = 2D(n-1) + 2 for n>1.

D(2) = _______________________________________________

D(3) = _______________________________________________

D(4) = _______________________________________________

10. Find the 3^rd, 4^th and 5^th values in the sequence.

D(1) = 1

D(2) = 4

D(n) = 2D(n-1) + D(n-2) for n>2.

D(3) = _______________________________________________

D(4) = _______________________________________________

D(5) = _______________________________________________

11. Using the SelectionSort algorithm on p 169 in your textbook, simulate the execution of the algorithm on the following list L; write the list after every exchange.

L: 9, 2, 4, 8, 6

_______________

Expert Solution

Colby Messinger answered 6 months ago

For each of the statements, begin a proof by contraposition and a proof by contradiction. This...

For each of the statements, begin a proof by contraposition and a proof by contradiction. This will include rewriting the statement, writing the assumptions, and writing what needs to be shown. From there, pick one of the two methods and finish the proof. a) For all integers m and n, if m + n is even the m and n are both even or m and n are both odd. b) For all integers a, b, and c, if a...

Use proof by contradiction to show that a cycle graph with an odd number of nodes...

Use proof by contradiction to show that a cycle graph with an odd number of nodes is not 2-colorable.

1. Give a direct proof that if n is an odd integers, then n3 is also...

1. Give a direct proof that if n is an odd integers, then n3 is also an odd integer. 2. Give a proof by contradiction that the square of any positive single digit decimal integer cannot have more than two decimal digits.

Contradiction proof conception Prove: If A is true, then B is true Contradiction: If A is...

Contradiction proof conception Prove: If A is true, then B is true Contradiction: If A is true, then B is false. so we suppose B is false and follow the step to prove. At the end we get if A is true then B is true so contradict our assumption However, Theorem: Let (xn) be a sequence in R. Let L∈R. If every subsequence of (xn) has a further subsequence that converges to L, then (xn) converges to L. Proof: Assume,...

4. Use a proof by contradiction to show that the square root of 3 is irrational....

4. Use a proof by contradiction to show that the square root of 3 is irrational. You may use the following fact: For any integer k, if k2 is a multiple of 3, then k is a multiple of 3. Hint: The proof is very similar to the proof that √2 is irrational. 5. Use a direct proof to show that the product of a rational number and an integer must be a rational number. 6. Use a proof by...

Let P(n) := ” If n^3 is odd then n is also odd.” I.e., if ∃k...

Let P(n) := ” If n^3 is odd then n is also odd.” I.e., if ∃k ∈ Z, n3 = 2k + 1, ∃b ∈ Z, n = 2b + 1 a) Prove P(n) by contraposition b) Prove P(n) contradiction c) Prove P(n) using induction

Write a combinatorial proof for 1 n + 2 ( n − 1 ) + 3...

Write a combinatorial proof for 1 n + 2 ( n − 1 ) + 3 ( n − 2 ) + ⋯ + ( n − 1 ) 2 + n 1 = ( n + 2 choose 3 ) .

(a) Use a direct proof to show that the product of two odd numbers is odd....

(a) Use a direct proof to show that the product of two odd numbers is odd. (b) Prove that there are no solutions in integers x and y to the equation 2x2 + 5y2 = 14. (c) Prove that the square of an even number is an even number using (a) direct proof, (b) an indirect proof, and (c) a proof by contradiction. Q. 2. Maximum score = 25 (parts (a) 9 points, part (b-i) and (b-ii) 8 points) (a)...

prove that if an even integer n is subtracted from an odd integer m. then m...

prove that if an even integer n is subtracted from an odd integer m. then m - n is odd.

Suppose that a and b are integers. (a) (5 pts) Use a proof by contradiction to...

Suppose that a and b are integers. (a) (5 pts) Use a proof by contradiction to prove the statement ”If a − b is even, then a and b have the same parity (that is, they are both even or both odd).” Carefully show your algebra. (b) (5 pts) Show that any odd integer cubed is also an odd integer. Carefully show your algebra. (c) (5 pts) Use your results from parts (a-c) in a direct proof to show that...