Difference between revisions of "SKE Algo II (Winter 2019)/Homework 0/Solution"
(Created page with "= Revisiting proofs 1 = ''These assignments were adapted from '''Discrete Mathematics''', Douglas E. Ensley and J. Winston Crawley, Wiley.'' == Implication A == Prove or di...") |
|||
| Line 6: | Line 6: | ||
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: ''' | ||
== Implication B == | == Implication B == | ||
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: ''' | ||
= Revisiting proofs 2 = | = Revisiting proofs 2 = | ||
| Line 18: | Line 22: | ||
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: ''' | ||
== Implication D == | == Implication D == | ||
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: ''' | ||
== Optional question: Implication E == | == Optional question: Implication E == | ||
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: ''' | ||
= Revisiting proofs 3 = | = Revisiting proofs 3 = | ||
| Line 38: | Line 48: | ||
* <math>n</math> must be 1 more than a multiple of 9, or | * <math>n</math> must be 1 more than a multiple of 9, or | ||
* <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: ''' | ||
== Exhaust B == | == Exhaust B == | ||
Prove or disprove that for any integer <math>n</math>, <math>n^2 + 2 </math> is even. | Prove or disprove that for any integer <math>n</math>, <math>n^2 + 2 </math> is even. | ||
| + | |||
| + | '''Solution: ''' | ||
== Exhaust C == | == Exhaust C == | ||
Prove or disprove that every integer not divisible by 3 had a square that is of the form <math>3k + 1</math>. | Prove or disprove that every integer not divisible by 3 had a square that is of the form <math>3k + 1</math>. | ||
| + | |||
| + | '''Solution: ''' | ||
= Revisiting proofs 4 = | = Revisiting proofs 4 = | ||
| Line 54: | Line 70: | ||
Prove that <math>n^2 + n</math> is even for any positive integers <math>n</math>. | Prove that <math>n^2 + n</math> is even for any positive integers <math>n</math>. | ||
| + | |||
| + | '''Solution: ''' | ||
== Induction B == | == Induction B == | ||
Prove that <math>\sum_{i=1}^{N} i = \frac{(n)(n+1)}{2}</math> for any positive integers <math>N</math>. | Prove that <math>\sum_{i=1}^{N} i = \frac{(n)(n+1)}{2}</math> for any positive integers <math>N</math>. | ||
| + | |||
| + | '''Solution: ''' | ||
== Induction C == | == Induction C == | ||
Prove that <math>\sum_{i=1}^{N} i^2 = \frac{(n)(n+1)(2n+1)}{6}</math> for any positive integers <math>N</math>. | Prove that <math>\sum_{i=1}^{N} i^2 = \frac{(n)(n+1)(2n+1)}{6}</math> for any positive integers <math>N</math>. | ||
| + | |||
| + | '''Solution: ''' | ||
Revision as of 11:23, 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:
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:
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:
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:
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:
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:
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:
