1

How to prove that the sum of the first $1+3+9+\cdots+3^n$ natural numbers is equal to $1^2+3^2+9^2+\cdots+(3^n)^2$?

I've tried induction, but I can't get through the induction step. The base is simple, but in the step I can only use the induction hypothesis in a way that would give me the conclusion that the sum of the first $1+3+9+\cdots+3^{n+1}$ is equal to the sum of the first $1+3+9+\cdots+3^n$ numbers, but also the sum of the remaining $3^{n+1}$ numbers, and I don't know how to proceed from here. Any hints would be helpful.

implicati0n
  • 1,459
  • Do you know the formula for the sum of an arithmetic sequence? – platty Aug 09 '17 at 22:47
  • @hardmath I think it's a little deeper than that - it's the sum of positive integers up to the sum of the geometric progression. Of course, this does allow you to compose the formulae if you know them and skip induction entirely. – platty Aug 09 '17 at 22:49
  • @platty Yes, I know the formula. – implicati0n Aug 09 '17 at 22:49
  • @hardmath I'm not sure I know what you're talking about so I don't think I'd be able to do it that way. – implicati0n Aug 09 '17 at 22:50
  • @implicati0n Hint: $;m=1+3+3^2+\dots+3^n=(3^{n+1}-1)/2,$, and the sum of the first $m$ natural numbers is $m(m+1)/2,$. P.S. Don't know why you tagged the question induction because you don't need induction (unless you insist on using it for some reason). – dxiv Aug 09 '17 at 22:50
  • In that case, you can also consider the set of the numbers from $\sum_{i=1}^n 3^i+1$ to $\sum_{i=1}^{n+1} 3^i$ as an arithmetic sequence and apply the formula for the induction step. – platty Aug 09 '17 at 22:52

1 Answers1

6

You don't need induction; you can actually show equality with a relatively well-known (though perhaps at first "tricky") summation technique:

Well first, what is $1+3+9+\cdots+3^n$? Define that quantity to be $N$, and note that $3N = 3+9+\cdots+3^n+3^{n+1} = N + 3^{n+1}-1$, so $2N = 3^{n+1}-1$, and $N = \frac12(3^{n+1}-1)$.

Now that you know how high you are summing, you get:

$$ S = \sum_{i=1}^Ni = \frac12N(N+1) = \frac18(3^{n+1}-1)(3^{n+1}+1) = \frac18(9^{n+1}-1) $$

Now, consider $S' = 1^2 + 3^2 + 9^2+\cdots + 3^{2n}$. Note that $9S' = 3^2 + 9^2 + \cdots + 3^{2n} + 3^{2n+2} = S' + 3^{2n+2} - 1$, so $8S' = 9^{n+1} - 1$, and $S' = \frac18(9^{n+1}-1)$.

Since $S' = S$, you are done.