Math 1210 Chapter 1 Notes (Sections 1.1 and 1.2)
fSection 1.1 - Mathematical Induction
Purpose: A method to prove that a statement P(n) is true for all positive integers n ≥ 1.
Core idea: Prove a base case and establish a mechanism that propagates truth from one case to the next.
Key components:
Base Case: Directly show th e statement is true for the first value (not necessarily n = 1, just the first value of interest).
Induction Hypothesis: Assume P(k) is true for some k ≥ 1.
Induction Step: Use the hypothesis to prove P(k+1) is true.
Notation: P(n) stands for the statement we want to prove (replace n with the appropriate variable).
Common phrasing:
Base case verification: P(1) is true (or P(m) for the first required m).
Induction rule: If P(k) is true, then P(k+1) is true for all k ≥ 1.
Conclusion: Since P(1) is true and P(k) ⇒ P(k+1) for all k ≥ 1, P(n) holds for all n ≥ 1.
How the induction chain works in practice:
We know the statement is true for n = 1 (base case).
Then, assuming it is true for n = k, we show it must be true for n = k + 1.
This creates an infinite domino effect: true for 1 ⇒ true for 2 ⇒ true for 3 ⇒ … and so on.
Important terminology (from the notes slides):
Base Case: direct verification for the first value(s).
Induction Hypothesis: the assumption that P(k) holds for some k ≥ 1.
Induction Step: demonstration that P(k) ⇒ P(k+1).
P(n): the statement being proven (useful shorthand instead of repeating the full statement).
Important nuance:
The base case does not necessarily have to be n = 1; it is simply the first value for which we want to establish truth.
Induction shows the statement is true for all n once both base case and induction step are established.
Classic examples provided in the notes:
Example A: Show that the sum of the first n positive integers equals n(n + 1)/2 for all integers n ≥ 1.
Base case (n = 1): 1 = 1(1+1)/2 = 1.
Induction step: assume ∑{i=1}^{k} i = k(k+1)/2. Then egin{aligned} \,\sum{i=1}^{k+1} i &= \Big(\sum_{i=1}^{k} i\Big) + (k+1) \
&= \frac{k(k+1)}{2} + (k+1) \
&= \frac{(k+1)(k+2)}{2}.
\end{aligned}Therefore, the formula holds for n = k+1, completing the induction.
Example B: Show that the sum of the first n squares equals n(n+1)(2n+1)/6 for all n ≥ 1.
Base case: n = 1 gives 1^2 = 1 = 1·2·3/6.
Induction step: assume ∑_{i=1}^{k} i^2 = k(k+1)(2k+1)/6; then compute for k+1 and show the target formula holds (standard induction derivation).
Example C (an exercise from the slides; note about a potential typo):
Statement given: Show 42n − 1 is divisible by 15 for all integers n ≥ 0.
Comment: This statement is not true for n = 0 (−1 is not divisible by 15) and for n = 1 (41 is not divisible by 15), indicating a likely typo in the slide. The induction framework would require a valid base case; a corrected version might be 42^n − 1 is divisible by 15 for all n ≥ 1 (which can be checked via induction).
Example D (another exercise from the slides):
Statement given: Show 2^n ? 4^n for all integers n ≥ 4. The exact printed form is unclear in the transcript (noted as “Show 2n4n”). The induction approach would depend on the precise inequality or relation intended.
Notes from page 9 (context for induction language):
Directly showing the base case establishes the starting point.
The induction hypothesis is the assertion P(k) for some k ≥ 1.
The base case does not have to be n = 1; the first value of interest is what P(n) must hold for.
Writing P(n) instead of repeating the entire statement helps readability.
Summary takeaway for Section 1.1:
Induction is a two-step proof technique: establish a base case and prove a step that upwardly propagates truth from n to n+1 (or from n = k to n = k+1).
The technique hinges on the logical structure: if P(k) then P(k+1) for all k ≥ 1, plus P(1) (or P(m)) true.
Use for all sorts of statements on positive integers, including sums, divisibility, and inequalities.
Section 1.2 - Sigma Notation
Motivation: We want a compact and systematic way to write sums like 1 + 2 + ··· + n.
What is sigma notation?
The sigma symbol ∑ is used to denote sums with a clear index, bounds, and a summand that depends on the index.
General form: \sum_{i=m}^{n} f(i), where i is the index, m is the lower bound, n is the upper bound, and f(i) is the summand.
Practical tips from the notes:
It is easier to express and manipulate sums when the terms are kept in the unsimplified form during setup.
The given examples illustrate translating verbal sums into sigma notation and then using standard formulas to evaluate.
Examples of translating sums to sigma notation (as shown in the slides):
Example A: √5/24 + √6/25 + √7/26 + ··· + √15/214.
Example B: 1/20 + 8/30 + 27/42 + 64/56 + 125/72 + 216/90 + 343/110.
Tip from the slides: It is easier to find the closed form when the terms are left in unsimplified form first.
More example style prompts from the slides:
Express and evaluate sums like 1 − 4 + 9 − 16 + 25 − 36 ± ··· + 361 − 400 (each term is a pattern that could be written with a sigma if a rule is identified).
Express and evaluate sums like 2^2 3? 5 + 7? 8? 9? (the exact formatting in the transcript is unclear; the point is to practice converting more complex term patterns into sigma notation).
Standard sigma notation evaluation rules that the slides emphasize:
Known closed forms:
\sum_{i=1}^{n} i = \frac{n(n+1)}{2}.
\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}.
\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2.
A natural question: what is a simple closed form for \sum_{i=1}^{n} 1?
Answer: \sum_{i=1}^{n} 1 = n.
Direct applications / worked examples (as given in the notes):
Example 1 (Problem 7 in the slides): Compute \sum_{i=1}^{7} \bigl(2i^2 + 3i + 2\bigr).
Break into parts: ∑(2i^2) + ∑(3i) + ∑(2).
Using the standard sums:
∑_{i=1}^{7} i^2 = 7·8·15/6 = 140, so ∑ 2i^2 = 280.
∑_{i=1}^{7} i = 7·8/2 = 28, so ∑ 3i = 84.
∑_{i=1}^{7} 2 = 2·7 = 14.
Total: 280 + 84 + 14 = 378.
Example 2 (Problem 10): Compute \sum_{i=1}^{4} (i+10)^2.
Expand: i^2 + 20i + 100.
Use known sums: ∑ i^2 from 1 to 4 = 30; ∑ i from 1 to 4 = 10;
∑ 100 over 4 terms = 400.Total: 30 + 20·10 + 400 = 30 + 200 + 400 = 630.
Example 3 (Problem 50): Compute \sum_{i=21}^{50} i^2.
Use the identity: ∑_{i=1}^{n} i^2 = n(n+1)(2n+1)/6.
∑{i=21}^{50} i^2 = ∑{i=1}^{50} i^2 − ∑_{i=1}^{20} i^2
= [50·51·101/6] − [20·21·41/6]
= 42,925 − 2,870 = 40,055.Example 4 (Problem 59): Compute \sum_{i=-30}^{59} (i^2 + i).
Split into two sums: ∑ i^2 + ∑ i over the range.
∑ i over -30 to 59 equals (number of terms) × (average term) = 90 × ( (-30 + 59) / 2 ) = 90 × 14.5 = 1,305.
For ∑ i^2 over -30 to 59: use symmetry around 0 to relate to positive indices:
∑{i=-30}^{59} i^2 = ∑{i=1}^{59} i^2 + ∑_{i=1}^{30} i^2
= [59·60·119/6] + [30·31·61/6] = 70,210 + 9,455 = 79,665.Total: 79,665 + 1,305 = 80,970.
Observations and tips from the sigma notation section:
Sigma notation helps compactly represent long sums and makes pattern recognition easier once the index and bounds are clear.
When evaluating, it’s often easiest to separate the summand into simpler components and use linearity: ∑(ai + bi) = ∑ai + ∑bi.
For polynomial summands, use the known closed-form sums for i, i^2, i^3, etc., to compute quickly.
Additional notes on the “two examples” mentioned in the slides:
The transcript references two more example forms involving fractions with powers and products in denominators. The exact expressions are garbled in the transcript, but the intent is to practice expressing complex terms in sigma notation and then evaluating with the index bounds provided.
Summary takeaway for Section 1.2:
Learn the notation and how to translate sums to sigma form.
memorize and apply the fundamental sum formulas for i, i^2, i^3, and basic constant sums.
Practice evaluating sums with various bounds (including negative indices) by splitting into known components and using identities.
Quick reference formulas to remember:
\sum_{i=1}^{n} i = \frac{n(n+1)}{2},
\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6},
\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2,
\sum_{i=1}^{n} 1 = n.