Can this inductive proof that $\sum_{i=0}^n2^{2i+1}=\frac23(4^n-1)$ be simplified?

222 Views Asked by At

The general structure of equations I've used for the inductive step for proofs with a summation is something like:

We'll prove that $\sum_{i = 0}^{n + 1} (\text{something}) = (\text{closed form expression})$

\begin{align} \sum_{i = 0}^{n + 1} (\text{something}) &= \sum_{i = 0}^n (\text{something}) + \text{last term} &\\ &= [\text{expression via I.H.}] + \text{last term} &\\ &= \text{do some work...} &\\ &= \text{some more work...} &\\ &= (\text{finally reach the closed form expression we want}) \end{align}

This structure is very nice, since the equation is one-sided, and very easy to follow. However I solved a problem that I couldn't solve with this one-sided structure, and I had to substitute the LHS with the closed form expression I'm trying to prove, so I could use some of its terms to simplify the RHS. This is fine and valid, but I'd like to know if there's a simpler way to perform this proof that doesn't employ the substitution you see below:

enter image description here

In other words, I couldn't figure out how to simplify $\frac{2}{3}(4^n - 1) + 2^{2n + 1}$ to get $\frac{2}{3}(4^{n + 1} - 1)$. The farthest I got was:

\begin{align} &= \frac{2}{3}(4^n - 1) + 2^{2n + 1} &\\ &= \frac{2}{3}(4^n - 1) + 2\cdot 2^{2n} &\\ &= \frac{2}{3}(4^n - 1) + 2\cdot 4^n &\\ &= \frac{2}{3}(4^n - 1) + \frac{3 \cdot 2\cdot 4^n}{3} &\\ &= \frac{2}{3}(4^n - 1 + 3 \cdot 4^n) &\\ \end{align}

3

There are 3 best solutions below

2
On BEST ANSWER

$$\frac{2}{3}(4^n - 1) + 2^{2n + 1}= \frac23\left(\color{red}{4^n}-1+\overbrace{\color{red}{3\cdot2^{2n}}}^{=3\cdot4^n}\right)=\frac23\left(\color{red}{4\cdot4^n}-1\right) = \frac{2}{3}(4^{n + 1} - 1)$$

1
On

Note that $2^{2n+1}=2\cdot 2^{2n}=2\cdot 4^n$. Now, $$\frac{2}{3}(4^n-1)+2^{2n+1}=\frac{2}{3}(4^n-1)+2\cdot 4^n =\frac{8}{3}\cdot 4^n -\frac{2}{3} = \frac{2}{3}(4^{n+1}-1)$$

0
On

You want to prove

$$\frac23(4^{n+1}-1)-\frac23(4^n-1)=2^{2n+1}.$$

Simplifying the $-1$ and dividing by $2\cdot4^n$, $$\frac13\cdot4-\frac13=1.$$


Note that this is just as case of the sum of a geometric progression

$$\sum_{k=0}^{n-1}ab^k=a\frac{b^n-1}{b-1},$$ proven by

$$ab^n=a\frac{b^{n+1}-1}{b-1}-a\frac{b^n-1}{b-1}=ab^n\frac{b-1}{b-1}.$$