1

I have tried for hours at this problem, but feel as if there is no way to prove it. Isn't this just false?

n > 0.

$$\sum_{k=0}^n \frac{1}{2^k} = 2 = \frac{1}{5^n}$$

I keep getting false because 2(left hand sided answer) is NOT equal to 3/2 (which is what I am getting on the right hand side) with the assumption that n =1. Am I attempting this problem correctly?

Ariani P.
  • 13
  • This is your friend for formatting math here: https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference – Sean Roberson Sep 06 '22 at 00:23
  • Thes sum $$\sum_{k=0}^1 \frac 1 {2^k}=\frac 3 2 = 2-\frac 1 {2^1} = \frac 3 2$$ – Seeker Sep 06 '22 at 00:34
  • 1
    For $n=1$ the LHS is $\frac{1}{2^0}+\frac{1}{2^1}=1+\frac{1}{2}=\frac{3}{2}$. –  Sep 06 '22 at 00:34
  • Therefore, it cannot be proven because they're not equal right? – Ariani P. Sep 06 '22 at 00:35
  • 1
    @They are equal for $n=1$ as shown in my comment above. Try adding the fractions on the L.H.S and subtracting the fractions on the R.H.S. – Seeker Sep 06 '22 at 00:36
  • 1
    And the RHS is $2-\frac{1}{2^1}=2-\frac{1}{2}=\frac{3}{2}$. So they are equal. –  Sep 06 '22 at 00:36
  • Wait, how - please? I thought 2 LHS MUST equal to 3/2 to continue the proof? – Ariani P. Sep 06 '22 at 00:37
  • 1
    For $n=1$, LHS is $\frac{3}{2}$. Not sure how you got $2$ there, it is wrong. Did you by any chance take $\sum_{k=0}^\infty$ rather than $\sum_{k=0}^n$? –  Sep 06 '22 at 00:38
  • 1
    Oh!! I definitely did not calculate correctly, I was unaware that 1/2^0 would be added to 1/2^1 – Ariani P. Sep 06 '22 at 00:42

3 Answers3

1

You're not starting out the problem correctly. Whenever you do a proof by induction, your base case should always be the lowest number in the set you're working with. In this case, we're working with $n \geq 0$. The lowest number in that set of nonnegative integers is $n=0$, so that's what your base case should be about. (Surely you can start at $n=1$, but then you'd also have to make a case where $n=0$ as well.)

Also, $n=1$ works because

$$\displaystyle\sum_{k=0}^{1} \frac{1}{2^k} = \frac{1}{2^0} + \frac{1}{2^1} = \frac{3}{2}$$

and

$$2 - \frac{1}{2^1} = \frac{3}{2}.$$

(Answer) The given statement you're trying to prove is true.

Base Step. If $n=0$, then

$$\sum_{k=0}^{0}\frac{1}{2^{k}}=\frac{1}{2^{0}}=1$$

and

$$2-\frac{1}{2^{0}} = 1.$$

Inductive Step. Fix some nonnegative integer $m \geq 0$ and suppose

$$\sum_{k=0}^{m}\frac{1}{2^{k}}=2-\frac{1}{2^{m}}.$$

Then

$$\sum_{k=0}^{m+1}\frac{1}{2^{k}}=\sum_{k=0}^{m}\frac{1}{2^{k}}+\frac{1}{2^{m+1}}\ =\ 2-\frac{1}{2^{m}}+\frac{1}{2^{m+1}}.$$

I think you can take it from here. Does that help?

Accelerator
  • 4,923
0

The first few sums look like this: $$\sum_{k=0}^0 \frac{1}{2^k} = 1=2-{1\over 2^0}$$ $$\sum_{k=0}^1 \frac{1}{2^k} = 1+\frac12=\frac32=2-{1\over 2^1}$$ $$\sum_{k=0}^2 \frac{1}{2^k} = 1+\frac12+\frac14=\frac74=2-{1\over 2^2}$$ $$\sum_{k=0}^3 \frac{1}{2^k} = 1+\frac12+\frac14+\frac18=\frac{15}8=2-{1\over 2^3}$$ So the thing you're being asked to prove seems to be correct.

Can you fill in the induction step yourself? It is quite simple.

Suzu Hirose
  • 11,660
  • Yes! I can attempt the induction! However, I was taught that we start with 1 always? Did you start with 0 because of the n >= 0? – Ariani P. Sep 06 '22 at 00:38
  • Yes, in this case we want to start at 0, otherwise as you say the calculation doesn't work. – Suzu Hirose Sep 06 '22 at 00:40
  • @ArianiP. You can start from $n=1$ all right, but then you have a special case $n=0$ to prove as well. So it works, but is more work to do. –  Sep 06 '22 at 00:44
0

Let's apply the binary system. We want to add $$1.\underbrace{11\ldots 11}_{n \ {\rm digits}}+0.\underbrace{00\ldots 01}_{n \ {\rm digits}}$$ We obtain $${\displaystyle\phantom{+}1.11\ldots 11\atop + \ \displaystyle\underline{0.00\ldots 01}}\atop \hspace{3pt}10.00\ldots 00$$ Hence $$\sum_{i=0}^n{1\over 2^i}+{1\over 2^n}=2$$

Ryszard Szwarc
  • 30,319