PG3.5 Stage review: two proofs of your own

Simulate

Check the first claim with numbers

This review asks for two proofs of your own: one by induction, one by strong induction. As always, each claim is tested first.

Grow $1 at a rate $x$ per period. Compounded for $n$ periods it becomes $(1 + x)^n$ ; with simple interest it becomes $1 + nx$ . The claim: compounding is never behind, $(1 + x)^n \ge 1 + nx$ .

from fractions import Fraction xs = [Fraction(-1), Fraction(-1, 2), Fraction(-1, 20), Fraction(0), Fraction(1, 20), Fraction(1), Fraction(10)] worst = min((1 + x) ** n - (1 + n * x) for x in xs for n in range(1, 51)) print("smallest value of (1 + x)^n - (1 + nx):", worst) for n in [1, 2, 10, 50]: print(n, round(1.05**n, 4), round(1 + 0.05 * n, 4))

⌘/Ctrl + Enter runs the cell

Over seven rates from $-1$ to 10 and 50 periods, the difference is never negative: its smallest value is exactly 0. At 5% the two agree for one period, at 1.05, and then compounding pulls ahead: 1.6289 against 1.5 after 10 periods.

⌘/Ctrl + Enter runs the cell

Rates far below $-1$ break the claim. With $x = -3$ the difference is $-18$ at $n = 5$ , and with $x = -4$ it is $-16$ at $n = 3$ . So the claim is stated for $x \ge -1$ , which makes $1 + x \ge 0$ : the proof needs exactly that.

Conjecture

x \ge -1

Every check with $x \ge -1$ agrees, but the claim is about every $n$ . It is called Bernoulli's inequality, and lesson PG4.5 uses it to show that $(1 + 1/n)^n$ converges.

Format 4

Write it: Bernoulli's inequality

Prove by induction that $(1 + x)^n \ge 1 + nx$ for every $x \ge -1$ and every $n \ge 1$ . Fix $x$ first, then write the base case, the inductive step and the conclusion, in sentences.

Your proof

Saved in this browser as you type.

Write your own first: a proof you have tried to write teaches far more than one you only read.

Simulate

Check the second claim with numbers

Every whole number seems to be a sum of different powers of 2, each used at most once: $13 = 8 + 4 + 1$ . Python's bin writes a number in base 2, and each digit 1 marks a power that is used.

def powers_of_two(n): """The different powers of 2 that add up to n, read from its base-2 digits.""" digits = bin(n)[2:] # bin(13) is '0b1101' return [2**i for i, d in enumerate(reversed(digits)) if d == "1"] for n in [1, 6, 13, 100]: print(n, bin(n), powers_of_two(n)) print(all(sum(powers_of_two(n)) == n for n in range(1, 10001)))

⌘/Ctrl + Enter runs the cell

For every $n$ from 1 to 10,000 the powers add up to $n$ ; for example, $100 = 4 + 32 + 64$ . The claim is special to 2, though. Try the same with powers of 3:

from itertools import combinations powers = [1, 3, 9, 27] sums = {sum(c) for k in range(1, 5) for c in combinations(powers, k)} print(len(sums), sorted(sums)) print([n for n in range(1, 41) if n not in sums])

⌘/Ctrl + Enter runs the cell

Different powers of 3 up to 27 make only 15 of the numbers from 1 to 40, and 2 is the first one missed. So the proof must use something true of 2 and not of 3.

Conjecture

n \ge 1

Ten thousand numbers agree, but the claim is about every $n$ . Its proof needs strong induction: the case it uses is about half of $n$ , not the case just before.

Format 4

Write it: sums of powers of 2

Prove by strong induction that every whole number $n \ge 1$ is a sum of different powers of 2. Hint: write $n = 2m$ or $n = 2m + 1$ , where $m$ is a smaller whole number.

Your proof

Saved in this browser as you type.

Write your own first: a proof you have tried to write teaches far more than one you only read.

The proof is also a method: halve $n$ , note the remainder, and repeat. The remainders, read from last to first, are the base-2 digits that bin prints.

(1 + x)^n \ge 1 + nx

Stage review: two proofs of your own

Check the first claim with numbers

Write it: Bernoulli's inequality

Check the second claim with numbers

Write it: sums of powers of 2

Summary card

Free further reading