Prove that for all $$n \ge 2$$, $$\sum_{i=2}^n i2^i = (n-1)2^{n+1}$$. --- #### Scratchwork $$\sum_{i=2}^n i2^i = 2 \cdot 2^2 + 3 \cdot 2^3 + \dots + n2^n$$. $$P$$? Isolate the part of the statement we want to prove, that is in terms of the "for all" variable, in this case, $$n$$. $$P(n)$$ is the statement "$$\sum_{i=2}^n i2^i = (n-1)2^{n+1}$$". Base case? Want to prove this statement for all $$n \ge 2$$. So at least one base case would be $$P(2)$$. If, for example, proving $$P(3)$$ can rely on $$P(2)$$ to be true, then $$P(3)$$ does not have to be a separate base case. Let's look at the inductive step: Consider some value of $$k$$ larger than the base case, so here, $$k > 2$$. And we assume for the inductive hypothesis that $$P$$ holds for all $$i$$ from $$2$$ to $$k-1$$. We need to prove $$P(k)$$ using $$P(2) \land \dots \land P(k-1)$$. Sometimes (often?) we can get away with actually just assuming $$P(k-1)$$. So let's try? $$P(k-1)$$ says $$\sum_{i=2}^{k-1} i2^i = ((k-1)-1)2^{(k-1)+1} = (k-2)2^k$$. And maybe adding $$k2^k$$ to both sides will give us $$P(k)$$. #### Proof Let $$P(n)$$ be the statement "$$\sum_{i=2}^n i2^i = (n-1)2^{n+1}$$". We proceed by induction on $$n$$. Base case: We prove $$P(2)$$. This is true because $$2 \cdot 2^2 = 8$$, and $$(2-1)2^{2+1} = 2^3 = 8$$. Inductive case: For $$k > 2$$, assume as our inductive hypothesis that $$P$$ holds for holds for all $$i$$ from $$2$$ to $$k-1$$. We need to prove $$P(k)$$. By $$P(k-1)$$, $$\sum_{i=2}^{k-1} i2^i = (k-2)2^k$$. Adding $$k2^k$$, $$\sum_{i=2}^k i2^i = (k-2)2^k + k2^k$$. Simplifying: $$\sum_{i=2}^k i2^i = (2k-2)2^k$$. Simplifying again: $$\sum_{i=2}^k i2^i = (k-1)2^{k+1}$$, which is $$P(k)$$. Alternatively: $$\sum_{i=2}^k i2^i = k2^k + \sum_{i=2}^{k-1} i2^i {\color{red} {}={}} k2^k + (k-2)2^k = (2k - 2)2^k = (k-1)2^{k+1}.$$ Induction complete. --- -- -- --- Prove that every positive integer can be written as a sum of distinct powers of 2. --- #### Scratchwork Good example: $$13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$$ Bad example: $$13 = 4 + 4 + 4 + 1 = 2^2 + 2^2 + 2^2 + 2^0$$, since $$2^2$$ is repeated. $$P(n)$$ can be the statement "$$n$$ can be written as a sum of distinct powers of 2". Base case: "every positive integer" so probably $$P(1)$$ Inductive case: Can we show $$P(k-1) \rightarrow P(k)$$? Example: if $$k = 13$$, then $$k - 1 = 12 = 2^3 + 2^2$$, and $$13 = 2^3 + 2^2 + 2^0$$. So it's tempting to say that in general, $$k = (k-1) + 2^0$$, and to apply $$P(k-1)$$. But: if $$k = 12$$, then $$k - 1 = 11 = 2^3 + 2^1 + 2^0$$, and then applying this idea would give $$12 = 2^3 + 2^1 + 2^0 + 2^0$$, which repeats $$2^0$$. This is bad. We could try to patch this by repeatedly combining terms. But that's complicated. An easier thing to do is the following: If $$k = 2^m$$ for some positive integer $$m$$ we don't have to do anything. Otherwise, let $$m$$ be the largest integer such that $$2^m < k$$. Set $$\ell = k - 2^m$$, and then $$k = \ell + 2^m$$, and we apply $$P(\ell)$$. Why should this work? The idea that $$\ell < 2^m$$. (Otherwise, let $$j = \ell - 2^m$$, then $$k = j + 2^m + 2^m = j + 2^{m+1}$$, violating that $$m$$ is the largest integer so that $$2^m < k$$. #### Proof Let $$P(n)$$ be the statement "$$n$$ can be written as a sum of distinct powers of 2". We proceed by induction on $$n$$. Base case: We prove $$P(1)$$. This is true because $$1 = 2^0$$. Inductive case: For $$k > 1$$, assume as our inductive hypothesis that $$P$$ holds for $$i$$ from $$1$$ to $$k-1$$. We prove $$P(k)$$. If $$k = 2^m$$ for some positive integer $$m$$, then $$k$$ is already the sum of distinct powers of $$2$$. Otherwise, let $$m$$ be the largest integer so that $$2^m < k$$. Set $$\ell = k - 2^m$$. The $$1 \le < k$$, so we can apply the inductive hypothesis: $$\ell$$ can be written as a sum of distinct powers of 2. Observe that $$\ell < 2^m$$, for otherwise $$\ell = j - 2^m$$ where $$j \ge 0$$, in which case $$k = j + 2^m + 2^m \ge 2^{m+1}$$, which is impossible since $$k$$ is not a power of $$2$$ and by definition of $$m$$. So $$2^m$$ is not part of the representation of $$\ell$$ as a sum of distinct powers of 2, so adding $$2^m$$ to this sum gives a representation of $$k$$ as a sum of distinct powers of 2. Induction complete. --- -- -- --- Bonus (not recorded): Prove that $$\sqrt{2}$$ is irrational. --- #### Proof: Let $$P(n)$$ be the statement "$$n/b \ne \sqrt{2}$$ for all positive integers $$b$$". Base case: $$P(1)$$: For all positive integers $$b$$, $$1/b \le 1 < \sqrt{2}$$. Inductive case: For $$k > 1$$ assume that $$P$$ holds for $$\ell$$ from $$1$$ to $$k-1$$. We prove the contrapositive of the statement: "If for all $$\ell$$ between $$1$$ and $$n-1$$, $$\ell/a \ne \sqrt{2}$$ for all positive integers $$a$$, then $$k/b \ne \sqrt{2}$$ for all positive integers $$b$$." The contrapositive is: "If $$k/b = \sqrt{2}$$ for some positive integer $$b$$, then there exists $$\ell$$ between $$1$$ and $$k-1$$ such that $$\ell/a = \sqrt{2}$$ for some positive integer $$a$$." Suppose that $$k/b = \sqrt{2}$$ for some positive integer $$b$$ Then $$k^2 = 2b^2$$, so $$k^2$$ is even. Since $$k^2$$ is even, $$k$$ is even, so set $$k = 2\ell$$ for some positive integer $$\ell$$. This results in $$(2\ell)^2 = 4\ell^2 = 2b^2$$, i.e., $$2\ell^2 = b^2$$, so $$b^2$$ is even. Since $$b^2$$ is even, $$b$$ is even, so set $$b = 2a$$ for some positive integer $$a$$. Then $$k/b = 2\ell/2a = \ell/a = \sqrt{2}$$. Since $$k > 1$$, $$\ell$$ is between 1 and $$k-1$$, and $$\ell/a = sqrt{2}$$ for some positive integer $$a$$. Induction complete. --- --- --- --- --- ---