Difference between revisions of "SKE Algo II (Winter 2019)/Homework 0/Solution"
| Line 7: | Line 7: | ||
Prove or disprove that for every integer <math>n \geq 1</math>, if <math>n</math> is odd then <math>n^2 + 4</math> is a prime number. | Prove or disprove that for every integer <math>n \geq 1</math>, if <math>n</math> is odd then <math>n^2 + 4</math> is a prime number. | ||
| − | '''Solution: ''' | + | '''Solution: ''' There exists <math>n = 9</math> that falsify the statement, thus the statement is false. |
== Implication B == | == Implication B == | ||
| Line 13: | Line 13: | ||
Prove or disprove that for every positive integer <math>n</math>, <math>2n^3</math> is divisible by 3. | Prove or disprove that for every positive integer <math>n</math>, <math>2n^3</math> is divisible by 3. | ||
| − | '''Solution: ''' | + | '''Solution: ''' There exists <math>n = 1</math> that falsify the statement, thus the statement is false. |
= Revisiting proofs 2 = | = Revisiting proofs 2 = | ||
| Line 23: | Line 23: | ||
Prove or disprove that for every positive integer <math>n</math>, if <math>n</math> is odd then <math>n^3-n</math> is divisible by 4. | Prove or disprove that for every positive integer <math>n</math>, if <math>n</math> is odd then <math>n^3-n</math> is divisible by 4. | ||
| − | '''Solution: ''' | + | '''Solution: ''' We can rewrite the term <math>n</math> in the form of <math>2k - 1</math> for any positive integers <math>k</math>. The term <math>n^3 - n</math> therefore can be rewritten in the form of |
| + | |||
| + | <math> | ||
| + | \begin{align} | ||
| + | n^3 - n &= (2k-1)^3 - (2k-1) \\ | ||
| + | &= 4 k (2 k^2 - 3 k + 1) | ||
| + | \end{align} | ||
| + | </math> | ||
| + | |||
| + | thus, the term is divisible by 4. | ||
== Implication D == | == Implication D == | ||
| Line 29: | Line 38: | ||
Prove or disprove that for all integers <math>n > 4</math>, if <math>n</math> can be expressed in the term of <math>z^2</math> for any integers <math>z</math>, then <math>n-1</math> is not a prime number. | Prove or disprove that for all integers <math>n > 4</math>, if <math>n</math> can be expressed in the term of <math>z^2</math> for any integers <math>z</math>, then <math>n-1</math> is not a prime number. | ||
| − | '''Solution: ''' | + | '''Solution: ''' We can rewrite the term <math>n-1</math> as <math>(z^2 - 1) = (z-1)(z+1)</math>, which is the product of two positive integers (since <math>n > 4</math>). Therefore, <math>n-1</math> is not a prime number as it could be written in the form of two positive integers' product. |
== Optional question: Implication E == | == Optional question: Implication E == | ||
| Line 35: | Line 44: | ||
Prove or disprove that for all integers <math>n</math>, if <math>n^2</math> is even then <math>n</math> is even. ''Hint: Use contrapositive.'' | Prove or disprove that for all integers <math>n</math>, if <math>n^2</math> is even then <math>n</math> is even. ''Hint: Use contrapositive.'' | ||
| − | '''Solution: ''' | + | '''Solution: ''' We instead going to prove that if <math>n</math> is odd then <math>n^2</math> is odd. We can rewrite the term <math>n</math> in the form of <math>2k - 1</math> for any positive integers <math>k</math>. Thus, <math>(2k - 1)^2 = 4k^2 - 4k + 1</math>, which is an odd number. Thus the proof. |
= Revisiting proofs 3 = | = Revisiting proofs 3 = | ||
| Line 49: | Line 58: | ||
* <math>n</math> must be 1 less than a multiple of 9. | * <math>n</math> must be 1 less than a multiple of 9. | ||
| − | '''Solution: ''' | + | '''Solution: ''' We proof the statement by observing all of its cases: |
| + | |||
| + | * If <math>n = 3p</math>, then <math>n^3 = 27p^3</math>, which is a multiple of 9. | ||
| + | * If <math>n = 3p+1</math>, then <math>n = 27 p^3 + 27 p^2 + 9 p + 1 = 9(3 p^3 + 3 p^2 + p) + 1</math>, which is 1 more than a multiple of 9. | ||
| + | * If <math>n = 3p-1</math>, then <math>n = 27 p^3 - 27 p^2 + 9 p - 1 = 9(3 p^3 - 3 p^2 + p) - 1</math>, which is 1 less than a multiple of 9. | ||
| + | |||
| + | Thus the proof. | ||
== Exhaust B == | == Exhaust B == | ||
Revision as of 11:37, 14 February 2020
Contents
Revisiting proofs 1
These assignments were adapted from Discrete Mathematics, Douglas E. Ensley and J. Winston Crawley, Wiley.
Implication A
Prove or disprove that for every integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \geq 1} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is odd then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2 + 4} is a prime number.
Solution: There exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 9} that falsify the statement, thus the statement is false.
Implication B
Prove or disprove that for every positive integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n^3} is divisible by 3.
Solution: There exists Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 1} that falsify the statement, thus the statement is false.
Revisiting proofs 2
These assignments were adapted from Discrete Mathematics, Douglas E. Ensley and J. Winston Crawley, Wiley.
Implication C
Prove or disprove that for every positive integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is odd then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^3-n} is divisible by 4.
Solution: We can rewrite the term Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} in the form of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2k - 1} for any positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . The term Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^3 - n} therefore can be rewritten in the form of
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} n^3 - n &= (2k-1)^3 - (2k-1) \\ &= 4 k (2 k^2 - 3 k + 1) \end{align} }
thus, the term is divisible by 4.
Implication D
Prove or disprove that for all integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n > 4} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} can be expressed in the term of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z^2} for any integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} is not a prime number.
Solution: We can rewrite the term Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (z^2 - 1) = (z-1)(z+1)} , which is the product of two positive integers (since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n > 4} ). Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} is not a prime number as it could be written in the form of two positive integers' product.
Optional question: Implication E
Prove or disprove that for all integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2} is even then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is even. Hint: Use contrapositive.
Solution: We instead going to prove that if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} is odd then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2} is odd. We can rewrite the term Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} in the form of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2k - 1} for any positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . Thus, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2k - 1)^2 = 4k^2 - 4k + 1} , which is an odd number. Thus the proof.
Revisiting proofs 3
Parts of these assignments were adapted from Discrete Mathematics, Douglas E. Ensley and J. Winston Crawley, Wiley.
Exhaust A
Proof that if an integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} can be written in the form of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z^3} for any integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z} , then it must satisfy one of the following critera:
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} must be a multiple of 9,
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} must be 1 more than a multiple of 9, or
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} must be 1 less than a multiple of 9.
Solution: We proof the statement by observing all of its cases:
- If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 3p} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^3 = 27p^3} , which is a multiple of 9.
- If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 3p+1} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 27 p^3 + 27 p^2 + 9 p + 1 = 9(3 p^3 + 3 p^2 + p) + 1} , which is 1 more than a multiple of 9.
- If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 3p-1} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 27 p^3 - 27 p^2 + 9 p - 1 = 9(3 p^3 - 3 p^2 + p) - 1} , which is 1 less than a multiple of 9.
Thus the proof.
Exhaust B
Prove or disprove that for any integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2 + 2 } is even.
Solution:
Exhaust C
Prove or disprove that every integer not divisible by 3 had a square that is of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3k + 1} .
Solution:
Revisiting proofs 4
In this section, use proof by induction to prove the given statement. Make sure to clearly indicate your steps of induction along with the induction hypothesis (I.H.).
Induction A
Prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2 + n} is even for any positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .
Solution:
Induction B
Prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{N} i = \frac{(n)(n+1)}{2}} for any positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} .
Solution:
Induction C
Prove that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{N} i^2 = \frac{(n)(n+1)(2n+1)}{6}} for any positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} .
Solution:
