Proofs

Claim: If n is an even integer, then n² is even.

1. Assume n is even. By definition, n = 2k for some integer k.
2. Then n² = (2k)² = 4k² = 2(2k²).
3. Since 2k² is an integer, n² = 2m where m = 2k² is an integer.
4. Therefore n² is even. ■

Claim: If n² is even, then n is even.

1. The contrapositive is: If n is odd, then n² is odd.
2. Assume n is odd, so n = 2k+1 for some integer k.
3. Then n² = 4k² + 4k + 1 = 2(2k²+2k) + 1, which is odd.
4. Since the contrapositive holds, the original statement holds. ■

Claim: √2 is irrational.

1. Assume, for contradiction, that √2 is rational: √2 = a/b in lowest terms.
2. Then 2 = a²/b², so a² = 2b², meaning a² is even, so a is even: a = 2c.
3. Substituting: 4c² = 2b² ⇒ b² = 2c², so b is also even.
4. But then a and b share a factor of 2, contradicting 'lowest terms'. ■

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

1. Base case: n=1. LHS = 1, RHS = 1(2)/2 = 1. True.
2. Inductive hypothesis: assume 1+2+...+k = k(k+1)/2 holds for some k ≥ 1.
3. Inductive step: 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2.
4. This matches the formula for n=k+1, so by induction the formula holds for all n ≥ 1. ■

Claim: For any integer n, n(n+1) is even.

1. Case 1: n is even. Then n = 2k for some integer k, so n(n+1) = 2k(n+1) = 2·[k(n+1)], which is even.
2. Case 2: n is odd. Then n+1 is even, so n+1 = 2k for some integer k, so n(n+1) = n·2k = 2·(nk), which is even.
3. Every integer is either even or odd, and both cases give an even result.
4. Therefore n(n+1) is even for every integer n. ■

Claim: Every integer n ≥ 2 can be written as a product of one or more primes.

1. Base case: n=2. 2 is itself prime, so it trivially is 'a product of one prime'.
2. Strong inductive hypothesis: assume every integer k with 2 ≤ k < n can be written as a product of primes.
3. Inductive step: consider n. If n is prime, we're done. Otherwise n = a·b with 2 ≤ a,b < n. By the strong hypothesis, both a and b can be written as products of primes, so n = a·b can too.
4. By strong induction, every integer n ≥ 2 is a product of primes. ■

Claim: For every full binary tree T (every node has 0 or 2 children), the number of leaves L(T) = the number of internal nodes I(T) + 1.

1. Base case: T is a single leaf node. Then L(T)=1, I(T)=0, and indeed 1 = 0+1.
2. Inductive hypothesis: assume the claim L=I+1 holds for the (structurally smaller) left subtree T1 and right subtree T2.
3. Inductive step: if T has a root with subtrees T1 and T2, then L(T) = L(T1)+L(T2), and I(T) = 1 + I(T1) + I(T2). By the hypothesis, L(T1)=I(T1)+1 and L(T2)=I(T2)+1, so L(T) = I(T1)+I(T2)+2 = (I(T)-1)+2 = I(T)+1.
4. By structural induction, the claim holds for every full binary tree. ■

Claim: Claim to disprove: For all integers n, n² + n + 1 is prime.

1. To disprove a 'for all' statement, it suffices to find a single value of n where it fails.
2. Try n = 4: n²+n+1 = 16+4+1 = 21.
3. 21 = 3 × 7, which is not prime.
4. Since the statement fails for n=4, it is false in general — this single counterexample disproves it. ■