0

I read it in a text saying they got there using standard techniques but I'm really rusty with this stuff because I've tried to prove it and don't seem to go anywhere.

kartzs96
  • 21
  • 3
  • You could try to prove it using induction – Mufasa Oct 27 '21 at 19:45
  • Hint: Try to prove it by induction. – Gábor Pálovics Oct 27 '21 at 19:45
  • 1
    I know I can prove it with induction, but how would I go if I needed to reach the right side just from the left side? – kartzs96 Oct 27 '21 at 19:54
  • 1
    Then please show us you know how to prove with induction. Without showing us what you tried, you wrote an empty claim. – amWhy Oct 27 '21 at 20:00
  • Multiply the two polynomials $(x-1) \times (1 + x + x^2 + \cdots + x^n) ~: ~n \in \Bbb{Z^+}$ to get some polynomial $f(x)$. Then conclude from this that $\displaystyle \frac{f(x)}{x - 1} = (1 + x + x^2 + \cdots + x^n) ~: ~x \neq 1.$ Then, apply this conclusion to your posted question. – user2661923 Oct 27 '21 at 20:38

1 Answers1

1

The first several terms being added are 1, 4, 16,64,256, and so on. So the first terms of the sum are:

$a_0=1$, $a_1=5$, $a_2=21 $,$a_3=85$, ...

Notice each term is 1 more than 4 times the previous term. Four times the first N terms produces N more terms of the sequence, N-1 that are already there, then essentially swapping the 1 with the next term in the sum. So add 1 to complete the series. This can be proven more rigorously with induction.

Frequently a formula for a sum can be deduced if you have two rules for generating subsequent terms.

We have both:

$a_{n+1}=a_n+4^{n+1}$, by definition of the series.

$a_{n+1}=4a_n +1$, by the above observation.

So $a_n+4^{n+1}=4a_n+1$.

Solve for $a_n$.

$a_n=\frac{4^{n+1}-1}{4-1}=\frac{2^{2n+2}-1}{3}$

TurlocTheRed
  • 5,683