Back MAT 243 — Visual Study Guide Math
Download Open
Show description 2,392 chars · Math

MAT 243 — Visual Study Guide

MAT 243 — Visual Study Guide

MAT 243
discrete math · visual guide

module 11 · companion

proofs, primes,& the patterns hiding in numbers

a visual reference for induction, divisibility, recursion, and linear recurrence relations. every concept shows its shape. every symbol earns its keep.

01 induction
02 IH
03 primes
04 gcd
05 lcm
06 recursion
07 rec. definitions
08 lin. recurrence
09 order
10 homogeneous
11 const. coefficients
12 lhcc
13 char. equation

01 / PROOF TECHNIQUE
mathematical induction

a two-step proof machine. prove it works for the first case. prove each case implies the next. logic does the rest. this is the domino effect written in math.

the mental model
every induction proof is a line of dominos

to prove infinitely many statements, you only need to prove two things:

base case — push the first domino (prove P(1) directly)

inductive step — show each domino knocks the next (if P(k) is true, then P(k+1) is true)

if both hold, every domino falls. that's the whole trick.

← first domino is the base case · rest fall by the inductive step →

push the first domino
reset

worked example
prove: 1 + 2 + 3 + ... + n = n(n+1)/2

click through each step of the proof. watch how the inductive hypothesis becomes the bridge from k to k+1.

claim: P(n): 1 + 2 + ... + n = n(n+1)/2 for all n ≥ 1

base case. show P(1) holds.

LHS = 1

RHS = 1(1+1)/2 = 2/2 = 1 ✓

inductive step. assume P(k) holds for some k ≥ 1.

inductive hypothesis (IH):

1 + 2 + ... + k = k(k+1)/2

show P(k+1) holds. target:

1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2

start with LHS:

1 + 2 + ... + k + (k+1)

= k(k+1)/2 + (k+1) ← substitute using IH

= (k+1)[k/2 + 1] ← factor out (k+1)

= (k+1)(k + 2)/2

= (k+1)(k+2)/2 ✓ ← matches target

by induction, P(n) holds for all n ≥ 1. ∎

next step →
← back
restart
step 0 / 16

template to memorize
every induction proof has the same skeleton

claim: P(n) is true for all n ≥ n₀

proof (by induction on n).

base case. show P(n₀) is true.
[plug in n₀, verify directly]

inductive step. assume P(k) for some k ≥ n₀. ← inductive hypothesis (IH)
we want to show P(k+1) is true.
[use IH to transform P(k) into P(k+1)]

therefore, by induction, P(n) holds for all n ≥ n₀. ∎

master the skeleton. the only part that changes problem-to-problem is the algebra in the inductive step.

02 / KEY TERM
the inductive hypothesis (IH)

the load-bearing assumption.…