-
-
Save dtinth/3903488 to your computer and use it in GitHub Desktop.
| <script type="text/x-mathjax-config">MathJax.Hub.Config({ TeX: { Macros: { | |
| 'NOT': '{\\sim}' | |
| , 'AND': '\\wedge' | |
| , 'OR': '\\vee' | |
| , 'IMPL': '\\rightarrow' | |
| , 'IMPLL': '\\Rightarrow' | |
| , 'IFF': '\\leftrightarrow' | |
| , 'IFFF': '\\Leftrightarrow' | |
| , 'EQUIV': '\\equiv' | |
| , 'taut': '\\textbf{t}' | |
| , 'cont': '\\textbf{c}' | |
| , 'ARG': ['\\begin{array} \\ #1 \\end{array}', 1] | |
| , 'PREM': ['& #1 \\\\ ', 1] | |
| , 'THAT': '\\text{ such that }' | |
| , 'SR': [ '\\left\\{ #1 \\right\\}', 1 ] | |
| , 'SB': [ '\\left\\{ #1 \\mid #2 \\right\\}', 2 ] | |
| , 'SUMM': ['\\sum _{#1=#2} ^{#3}', 3] | |
| , 'PRODD': ['\\prod _{#1=#2} ^{#3}', 3] | |
| , 'CONC': ['\\therefore & #1', 1] | |
| , 'S': ['\\frac{2^{#1}-1}{2^{#1-1}}', 1] | |
| , 'DS': ['\\scriptsize \\text{(#1)}', 1] | |
| , 'PS': '\\mathscr{P}' | |
| }}}) | |
| </script> |
| $(function() { | |
| $('.container > blockquote').each(function() { | |
| var $this = $(this) | |
| $this.hide().before($('<a class="btn btn-large" href="javascript://">Show Solution</a>').click(function() { | |
| $(this).hide() | |
| $this.show() | |
| })) | |
| }) | |
| }) |
Is this argument valid?
Valid Argument.
Actually, this problem is in Discrete Mathematics with Applications by Susanna S. Epp, Problem 41 of Section 2.3, with (\NOT) replaced with (\neg) and (t) becomes (w).
You can find the solution at the back of that book.
Prove or disprove that if (a) does not divide (bc), then (a) does not divide (b) too.
Valid Statement.
The contrapositive is: if (a) divides (b), then (a) also divides (bc).
So suppose that (a) divides (b), that is, (b = ak) for some integer (k),
we must show that (a) divide (bc) too, that is, (bc = al) for some integer (l).
But since we suppose that (b = ak), we can substitute it in to get:
$$ akc = al $$
Since we suppose that (a) divides (b), then (a) cannot be (0). Divide both sides by (a):
$$ kc = l $$
(\therefore bc = al) for (l = kc), and since (k) and (c) are integers, (kc) and therefore (l) are also integer, because the product of integers is an integer.
(\therefore bc) is divisble by (a). Quod erat demonstrandum.
Given a summation: (1
- \cfrac{1}{2}
- \cfrac{1}{2^2}
- \cfrac{1}{2^3}
- \cfrac{1}{2^4}
- \dotsb
- \cfrac{1}{2^n} ) for integer (n \ge 1), find:
-
Closed formula for the summation.
-
Recursive formula for the summation.
-
( \begin{array}{l} S_1 = 1 \ S_n = S_{n - 1} + \frac{1}{2^{n - 1}} \end{array} )
-
( S_n = \S{n} )
The summation is from this sequence:
$$1 , \frac{1}{2} , \frac{1}{2^2} , \frac{1}{2^3} , \frac{1}{2^4} , \dotsc , \frac{1}{2^n} , \dotsc $$
We can find its closed form:
$$ a_n = \left{ \begin{array}{ll} 1 & n = 0 \\ \frac{1}{2^n} & n > 0 \end{array} \right. $$
We can be sure that it's correct that by substituting (n) for 1, 2, 3, 4, and n, because that's what was given in the example.
Then, create a summation from sequence:
$$ S_n = \left{ \begin{array}{ll} a_0 & n = 1 \\ S_{n - 1} + a_{n - 1} & n > 1 \end{array} \right. $$
Therefore, the recursive formula is:
$$ \begin{array}{lll} S_1 & = & 1 \\ S_n & = & S_{n - 1} + \frac{1}{2^{n - 1}} \end{array} $$
By writing the first few terms from the recursive formula, we see that
$$ \begin{array} \ S_1 & = & 1 & = & \frac{1}{1} & = & \S{1} \ S_2 & = & 1 + \frac{1}{2} & = & \frac{3}{2} & = & \S{2} \ S_3 & = & \frac{3}{2} + \frac{1}{4} & = & \frac{7}{4} & = & \S{3} \ S_4 & = & \frac{7}{4} + \frac{1}{8} & = & \frac{15}{8} & = & \S{4} \ & \vdots \end{array} $$
Guess: The closed formula could be:
$$ S_n = \S{n} $$
Let (P(n) : S_n = \S{n})
Base Case: Show that P(2) is true:
$$ S_2 = 1 + \frac{1}{2} = \frac{3}{2} = \S{2} $$
Inductive Hypothesis: Suppose (P(n)), that is, suppose that this is true:
$$ S_n = \S{n} $$
Inductive Steps: We have to show that (P(n+1)) follows, that is:
$$ S_{n+1} = \S{n+1} $$
The right-hand side of this equation is:
$$ \S{n+1} = \frac{2^{n+1}-1}{2^n} $$
The left-hand side of this equation is:
$$ \begin{array} \ S_{n+1} & = & S_n + \frac{1}{2^n} & \DS{by the recursive definition} \ & = & \frac{2^n - 1}{2^{n-1}} + \frac{1}{2^n} & \DS{by inductive hypothesis} \ & = & \frac{2}{2} \cdot \frac{2^n - 1}{2^{n-1}} + \frac{1}{2^n} \ & = & \frac{2 \cdot 2^n - 2}{2^n} + \frac{1}{2^n} \ & = & \frac{2^{n+1} - 2 + 1}{2^n} \ & = & \frac{2^{n+1} - 1}{2^n} \end{array} $$
Since the left-hand side and the right-hand side has the same value, the equation is true.
Since we have proved the closed formula to be correct, the closed formula is:
$$ S_n = \S{n} $$
Prove or disprove that ( 5^n - 1 ) is divisible by (4), for (n \ge 0).
Valid Statement.
Let (P(n) : 4 \mid 5^n - 1 )
Base Case: Show (P(0)):
$$ 5^0 - 1 = 0 = 4 \cdot 0 . \ \therefore 4 \mid 5^0 - 1 $$
Inductive Hypothesis: Suppose that (P(n)) is true, that is (4 \mid 5^n - 1), that is, (5^n - 1 = 4k) for some integer (k).
Inductive Steps: We must show that (P(n+1)) follows, that is, (4 \mid 5^{n+1} - 1), that is (5^{n + 1} - 1 = 4l) for some integer (l).
From the inductive hypothesis, (5^n - 1 = 4k) and thus (5^n = 4k + 1).
$$ \begin{array} \ 5^{n + 1} - 1 & = & 5 \cdot 5^n - 1 \ & = & 5 \cdot (4k + 1) - 1 & \DS{by inductive hypothesis} \ & = & 20k + 5 - 1 \ & = & 20k + 4 \ & = & 4(5k + 1) \end{array} $$
(\therefore 5^{n+1} - 1 = 4l ) for (l = 5k + 1), and since (k) is an integer, (5k + 1) and therefore (l) are also integer, because the product and sum of integers are integers.
(\therefore 4 \mid 5^{n+1}).