I think that the sum 1+2+4+8+16+32+...+n is equal to 2n-1. At least it has worked on all the cases I've tried with, but I can't manage to prove it using induction. I am a newbie when it comes to proofs by induction, so am I doing the induction part wrong or is the sum actually not equal to 2n-1? If it is, could someone post the proof?
My try on the induction: 1+2+4+8+...+n = 2n-1
1+2+4+8+...+n+(n+1) = 2n-1+(n+1)
1+2+4+8+...+n+(n+1) = 3n
But 3n is not 2(n+1)-1 = 2n+1
HINT: The mistake in your induction proof is that the next element is not $n + 1$, but rather $2 \cdot n$.
Suppose $1+2+4+\ldots+2^k = 2\cdot2^k-1$ is valid $\forall k < n$, then prove it for $k=n$, and you're done (the base case is trivial, $k=1$). But note that you have: $$1+2+4+ \ldots 2^{n} = 1+2+4+ \ldots 2^{n-1} + 2^{n} = 2 \cdot 2^{n-1}-1+2^n=2^n-1+2^n=2\cdot2^n-1$$ and this is what you wanted to prove!
Hint. You're better off proving a differently worded (but in this case equivalent) claim, that
$$ 1+2+4+\cdots+2^n = 2^{n+1}-1 = 2(2^n)-1 $$
For the basis, obviously
$$ 2^0 = 1 = 2(2^1)-1 $$
For the induction, consider that in the expression
$$ 1+2+4+\cdots+2^{n-1}+2^n $$
one can collapse $1+2+4+\cdots+2^{n-1}$ into a single term from the induction premise.
$2^n - 1$becomes $2^n - 1$, while$2^{n - 1}$becomes $2^{n - 1}$. I also think you want to stop the sum not at $n$, but at $2^{n - 1}$. – pjs36 Dec 01 '15 at 18:01