Neural Sync Active

Advanced Proof Techniques

Registry Synced

161 words

1 min read

Reading compass

Now · Proof by Cases

Proof by Cases

Example: Prove

n^3 - n

is divisible by 3 for all integers

n

. Proof: Consider

n = 3k

3k+1

, or

3k+2

(all integers are one of these forms by division algorithm).

$n = 3k$ : $n^3 - n = 27k^3 - 3k = 3(9k^3 - k)$ ✓
$n = 3k+1$ : $n^3 - n = (27k^3 + 27k^2 + 9k + 1) - (3k+1) = 27k^3 + 27k^2 + 6k = 3(9k^3 + 9k^2 + 2k)$ ✓
$n = 3k+2$ : $n^3 - n = (27k^3 + 54k^2 + 36k + 8) - (3k+2) = 27k^3 + 54k^2 + 33k + 6 = 3(9k^3 + 18k^2 + 11k + 2)$ ✓

Prove

\sum_{k=0}^n \binom{n}{k} = 2^n

: Combinatorial argument: The RHS counts subsets of an

n

-element set. The LHS sums the number of subsets of each size

k