SKE Algo II (Winter 2019)/Homework 0/Solution - Revision history

Srakrn: /* Induction C */

2020-02-14T14:40:48Z

Induction C

Srakrn: /* Induction C */

2020-02-14T14:40:23Z

Induction C

Srakrn: /* Induction C */

2020-02-14T14:38:30Z

Induction C

Srakrn: /* Induction B */

2020-02-14T14:33:28Z

Induction B

Srakrn: /* Induction B */

2020-02-14T14:31:21Z

Induction B

Srakrn: /* Induction B */

2020-02-14T14:27:27Z

Induction B

Srakrn: /* Induction A */

2020-02-14T14:11:35Z

Induction A

Srakrn: /* Induction A */

2020-02-14T14:11:01Z

Induction A

Srakrn: /* Exhaust B */

2020-02-14T04:38:30Z

Exhaust B

Srakrn at 04:37, 14 February 2020

2020-02-14T04:37:46Z

@@ Line 153: / Line 153: @@
 &= \frac{(x)(x+1)(2x+1)+(6x+x)}{6}\\
 &= \frac{(x)(x+1)(2x+1)}{6} +(6x+x)\\
-&= \sum_{i=1}^{x} i^2 + (x+1)
+&= \sum_{i=1}^{x} i^2 + (x+1)^2
 \end{aligned}
 </math>
 Therefore, with mathematical induction, we've proven that <math>P(x)</math> holds true for all positive integer <math>x</math>, thus the proof.

@@ Line 151: / Line 151: @@
 \begin{aligned}
 \sum_{i=1}^{x+1} i^2 &= \frac{(x+1)(x+2)(2x+3)}{6}\\
-&= \frac{(x)(x+1)(2x+1)+(6x+x)}{6}
+&= \frac{(x)(x+1)(2x+1)+(6x+x)}{6}\\
-&= \frac{(x)(x+1)(2x+1)}{6} +(6x+x)
+&= \frac{(x)(x+1)(2x+1)}{6} +(6x+x)\\
 &= \sum_{i=1}^{x} i^2 + (x+1)
 \end{aligned}

← Older revision		Revision as of 14:38, 14 February 2020
Line 139:		Line 139:

	'''Solution: '''		'''Solution: '''
		+
		+	Consider <math>P(x)</math> as a statement claiming that <math>\sum_{i=1}^{x} i^2 = \frac{(x)(x+1)(2x+1)}{6}</math>.
		+
		+	''Base case:'' We begin our proof by considering <math>P(1)</math>. Since <math>\sum_{i=1}^{1} i^2 = \frac{(1)(x+1)(2x+1)}{6} = 1</math>, our statement holds true.
		+
		+	''Induction Hypothesis (I.H.):'' Assuming <math>P(x)</math> holds true, therefore assuming <math>\sum_{i=1}^{x} i^2 = \frac{(x)(x+1)(2x+1)}{6}</math> for any positive integers <math>x</math>.
		+
		+	''Inductive step'': We proof that <math>P(x+1)</math> holds true, thus we need to show that <math>\sum_{i=1}^{x} i^2 = \frac{(x+1)(x+2)(2x+3)}{6}</math>.
		+
		+	<math>
		+	\begin{aligned}
		+	\sum_{i=1}^{x+1} i^2 &= \frac{(x+1)(x+2)(2x+3)}{6}\\
		+	&= \frac{(x)(x+1)(2x+1)+(6x+x)}{6}
		+	&= \frac{(x)(x+1)(2x+1)}{6} +(6x+x)
		+	&= \sum_{i=1}^{x} i^2 + (x+1)
		+	\end{aligned}
		+	</math>
		+
		+	Therefore, with mathematical induction, we've proven that <math>P(x)</math> holds true for all positive integer <math>x</math>, thus the proof.

← Older revision		Revision as of 14:33, 14 February 2020
Line 111:		Line 111:

	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:'''

	Consider <math>P(x)</math> as a statement claiming that <math>\sum_{i=1}^{x} i = \frac{(x)(x+1)}{2}</math>.		Consider <math>P(x)</math> as a statement claiming that <math>\sum_{i=1}^{x} i = \frac{(x)(x+1)}{2}</math>.

@@ Line 124: / Line 124: @@
 \sum_{i=1}^{x+1} i &= \frac{(x+1)(x+2)}{2}\\
 &= \frac{x^2 + 3x + 2}{2}\\
-&= \frac{x^2 + 2x + 1}\\
+&= \frac{(x)(x+1)+2(x+1)}{2}\\
-&= \frac{x(x+1)+2(x+1)}{2} = \frac{x(x+1)}{2}(x+1)\\
+&= \frac{x(x+1)}{2}(x+1)\\
-&= \sum_{i=1}^{x} i = \frac{(x)(x+1)}{2} + (x+1)
+&= \sum_{i=1}^{x} i + (x+1)
 \end{aligned}
 </math>

@@ Line 110: / Line 110: @@
 == 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: '''
+Consider <math>P(x)</math> as a statement claiming that <math>\sum_{i=1}^{x} i = \frac{(x)(x+1)}{2}</math>.
 == Induction C ==

@@ Line 99: / Line 99: @@
 \begin{aligned}
 (x + 1)^2 + (x + 1) &= x^2 + 2x + 1 + x + 1\\
-&= x^2 + 3x + 2
+&= x^2 + 3x + 2\\
 &= (x^2 + x) + (2x + 2)
 \end{aligned}

← Older revision		Revision as of 14:11, 14 February 2020
Line 87:		Line 87:

	'''Solution: '''		'''Solution: '''
		+
		+	Consider <math>P(x)</math> as a statement claiming that <math>x^2 + x</math> is even.
		+
		+	''Base case:'' We begin our proof by considering <math>P(1)</math>. Since <math>1^2 + 1 = 2</math>, our statement holds true.
		+
		+	''Induction Hypothesis (I.H.):'' Assuming <math>P(x)</math> holds true, therefore assuming <math>x^2 + x</math> is even for any positive integers <math>x</math>.
		+
		+	''Inductive step'': We proof that <math>P(x+1)</math> holds true, thus we need to show that <math>(x + 1)^2 + (x + 1)</math> is even.
		+
		+	<math>
		+	\begin{aligned}
		+	(x + 1)^2 + (x + 1) &= x^2 + 2x + 1 + x + 1\\
		+	&= x^2 + 3x + 2
		+	&= (x^2 + x) + (2x + 2)
		+	\end{aligned}
		+	</math>
		+
		+	Since <math>(x^2 + x)</math> is even by our induction hypothesis and <math>2x + 2</math> is trivially an even number, the summation of the two terms will be an even number.
		+
		+	Therefore, with mathematical induction, we've proven that <math>P(x)</math> holds true for all positive integer <math>x</math>, thus the proof.

	== Induction B ==		== Induction B ==

@@ Line 70: / Line 70: @@
 Prove or disprove that for any integer <math>n</math>, <math>n^2 + 2 </math> is even.
-'''Solution: '''
+'''Solution: ''' We consider a counterexample of <math>n=1</math> which falsify the statement.
 == Exhaust C ==

@@ 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.
-'''Solution: '''
+'''Solution: ''' There exists <math>n = 9</math> that falsify the statement, thus the statement is false.
 == 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.
-'''Solution: '''
+'''Solution: ''' There exists <math>n = 1</math> that falsify the statement, thus the statement is false.
 = 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.
-'''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
 == 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.
-'''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 ==
@@ 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.''
-'''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 =
@@ Line 49: / Line 58: @@
 * <math>n</math> must be 1 less than a multiple of 9.
-'''Solution: '''
+'''Solution: ''' We proof the statement by observing all of its cases:
 == Exhaust B ==