Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please help. I haven't found any text on how to prove by induction this sort of problem:

$$ \lim_{n\to +\infty}1 + \frac{1}{4} + \frac{1}{4^2} + \cdots+ \frac{1}{4^n} = \frac{4}{3} $$

I can't quite get how one can prove such. I can prove basic divisible "inductions" but not this. Thanks.

share|improve this question
5  
You can't prove it because it's false for every $n\in \Bbb N$. –  Git Gud May 5 '13 at 16:30
3  
I think you to need establish the partial sum using induction, then make $n\to\infty$ –  lab bhattacharjee May 5 '13 at 16:32
1  
@GitGud : is there a typo in your comment? I don't see how $m$ is used. –  Stefan Smith May 5 '13 at 16:43
1  
@Mob : you need to find the value of a finite geometric series and take its limit as $n \to \infty$. Do you have a calculus book? The answer you seek may be in there? –  Stefan Smith May 5 '13 at 16:45
1  
Amazing how many people don't instantly remember that this was done by Archimedes. –  Michael Hardy May 5 '13 at 16:48

10 Answers 10

Archimedes did this (Thomas Heath's translation of Quadrature of the Parabola, Proposition 23). He showed that (expressed in modern notation) $$ \underbrace{1+\frac14+\frac1{4^2}+\cdots+\frac1{4^n}}+\underbrace{\frac13\left(\frac1{4^n}\right)} $$ does not depend on the number of terms. All you have to do is show that when you go the the next term, the sum doesn't change. When you go to the next term, you get $$ \underbrace{1+\frac14+\frac1{4^2}+\cdots+\frac1{4^n}+\frac1{4^{n+1}}}+\underbrace{\frac13\left(\frac1{4^{n+1}}\right)}. $$ But you have changed $$ \frac13\left(\frac1{4^n}\right) $$ to $$ \frac1{4^{n+1}}+\frac13\cdot\frac1{4^{n+1}}. $$ The problem then is just to show that those two things are equal. If you multiply both by $4^n$, then one of them becomes $$ \frac13 $$ and the other becomes $$ \frac14+\frac13\cdot\frac14. $$ It's easy to show that those are equal.

Since the sum does not depend on the number of terms, the sum is just what you get when $n=0$: $$ 1+\frac13. $$

The method used by Archimedes perhaps cannot be regarded as an instance of mathematical induction, but it suggests at once how to write it as a proof by induction.

Latter note: Thomas Heath translates Proposition 23 of Archimedes' Quadrature of the Parabola as follows:

Given a series of areas $A,B,C,D,\cdots Z$ of which $A$ is the greatest, and each is equal to four times the next in order, then $$ A+B+C+\cdots+Z + \frac13 Z = \frac43 A. $$

Still later note: Here's what this has to do with parabolas: Given a secant line to a parabola, draw a line through its midpoint parallel to the axis, thus.

Then draw the two additional resulting secant lines, making a triangle, and construct triangles on top of those two secant lines, in the same way, thus.

Archimedes showed that the two small triangles have a total area that is $1/4$ of that of the big triangle. Then notice that the process can be continued forever, getting the area bounded by the parabola and the first secant line equal to $4/3$ the area of that big triangle.

share|improve this answer
    
Thanks for providing this additional information. However, after looking carefully at the link provided I don't agree that Archimedes's proof is by induction. If you look at the algebraic translation given by Heath there is no logical reduction of the $n+1$ case to the $n$ case: the argument for a given parameter $n$ is established directly. You could choose to recast the argument in inductive terms -- as you have -- but this is not what Archimedes actually says (or needs to say). In fact, isn't his argument really a version of the telescoping sum approach? –  Pete L. Clark May 5 '13 at 18:10
1  
To me, the clincher that it is not an inductive argument is that, as expressed in my answer, it does not assume the answer in advance for any parameter value. Rather it derives the answer for any given $n$. (This is better than an inductive argument, it seems to me.) –  Pete L. Clark May 5 '13 at 18:14
    
Regardless of whether it's an inductive argument (and necessarily one would have to a certain amount of adapting to modern concepts to make it fully such an argument), it instantly suggests (to us who live today) how to do it by induction. –  Michael Hardy May 5 '13 at 18:21
1  
By the way, the one "ancient" argument I've seen that really does look like an induction to me is Euclid's proof of the infinitude of primes. Precisely what he does is to assume that there are $n$ primes and produces another one. Part of the brilliance of this argument is that it seems so isolated in mathematical history, by thousands of years. People don't seem to want to think of Euclid's proof as inductive; rather they want to view it as a proof by contradiction, which is an underselling of it. I know you'll agree with me on that, at least. –  Pete L. Clark May 5 '13 at 18:21
2  
As I said, I think construing Archimedes's argument as an induction is weakening it a bit. It is somehow better not to prove something by induction if possible, and Archimedes's argument gives a non-inductive proof. –  Pete L. Clark May 5 '13 at 18:23

If you want to use proof by induction, you have to prove the stronger statement that

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

share|improve this answer

After subtracting $1$ this is equivalent to $\frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \cdots = \frac{1}{3}$. Behold:

enter image description here

Image taken from here.

share|improve this answer
2  
The lack of objectivity of mathematicians never ceases to amaze me. This answer is leading on upvotes and it doesn't even answer the question. –  Git Gud May 5 '13 at 16:40
4  
Love the "Behold"! and the big triangle. –  Lord Soth May 5 '13 at 16:43
3  
@GitGud That depends on what you consider a proof. This picture can lead to a proof, by induction even. –  Quinn Culver May 5 '13 at 16:45
1  
@GitGud And maybe you're mistaking another phenomenon for a lack of objectivity. E.g. maybe it's just that this is a pretty answer and somehow 'better' than an induction proof. Perhaps it will help the OP more than the objective answer. –  Quinn Culver May 5 '13 at 16:48
1  
@GitGud By induction, $\frac{1}{4} + \frac{1}{4^2} + ...+ \frac{1}{4^n} = \frac{1}{3} - \frac{1}{3}\frac{1}{4^n} $ –  Quinn Culver May 5 '13 at 16:49

The below image can easily be made into an inductive proof.

enter image description here

To be precise, the above image first shows that $$\dfrac12 + \dfrac14 + \dfrac18 + \cdots = 1$$ and then shows that

$$\dfrac1{2^2} + \dfrac1{(2^2)^2} + \dfrac1{(2^3)^2} + \dfrac1{(2^4)^2} + \cdots = \dfrac13$$ which implies $$\dfrac1{4} + \dfrac1{4^2} + \dfrac1{4^3} + \dfrac1{4^4} + \cdots = \dfrac13$$

share|improve this answer
4  
@AustinMohr There is an induction. In fact, induction is very strongly seen in this picture. Each level, the area of the red square equals $\dfrac1{3^{rd}}$ the area of the green $L$ shaped region. Hence, the sum of the areas of the red squares up-to a certain level equals $1/3^{rd}$ the sum of the areas of the green square up-to a certain level and now letting $n \to \infty$, we get what we want. –  user17762 May 5 '13 at 16:53
1  
Thanks for the nice picture! But it's not a proof by induction. –  TonyK May 5 '13 at 21:14
    
@TonyK As I have mentioned in the above comment, it is in fact a proof by induction. –  user17762 May 5 '13 at 21:14

i have a solution, but not seem mathematical induction

$s = 1 + \dfrac1{4} + \dfrac1{4^2} + \dfrac1{4^3} + \dfrac1{4^4} + \cdots$

$\dfrac1{4}s = \dfrac1{4} + \dfrac1{4^2} + \dfrac1{4^3} + \dfrac1{4^4} + \dfrac1{4^5} + \cdots$

$\dfrac1{4}s = - 1 + (1 + \dfrac1{4} + \dfrac1{4^2} + \dfrac1{4^3} + \dfrac1{4^4} + \dfrac1{4^5} + \cdots)$

$\dfrac1{4}s = - 1 + s$

$\dfrac3{4}s =1$

$s = \dfrac4{3}$

share|improve this answer
    
Nice, exactly what I was thinking. I'm at a loss what's meant by induction in this context. –  JoeTaxpayer Jun 2 '13 at 14:45

The statement of your question is quite confused. Clearly $1 + \frac{1}{4} + \ldots + \frac{1}{4^n}$ is a quantity that gets larger with $n$ -- you're adding on more positive numbers -- so it cannot be equal to any fixed number.

I think what you want to show by induction is:

For every real number $a \neq 1$ and every positive integer $n$, $1 + a + \ldots + a^n = \frac{1-a^{n+1}}{1-a}$.

The setup here is the usual one for the easiest inductions: you check the base case ($n=1$), then for an arbitrary positive integer $n$ you assume that $1 + a + \ldots + a^n = \frac{1-a^{n+1}}{1-a}$. Then you add the next term -- here $a^{n+1}$ -- to both sides and do at little algebra to show that you get what you're supposed to: here, $\frac{1-a^{n+2}}{1-a}$. If you can do any induction proofs you can probably do this without much trouble; please try it.

Now:

1) If $|a| < 1$, then $\lim_{n \rightarrow \infty} a^{n+1} = 0$, so

$\lim_{n \rightarrow \infty} (1+a + \ldots + a^n) = \sum_{n=0}^{\infty} a^n = \frac{1}{1-a}$.

If you plug in $a = \frac{1}{4}$ you'll get the single identity that I think you're asking for. This is one of the very first and most important instances of finding the sum of an infinite series. One often spends much of an entire course studying such things, e.g. towards the end of second semester calculus.

2) Most people would prefer not to establish the boxed identity by induction. This is because of the "kryptonite" inherent in the otherwise superstrong method of proof by induction: you must know in advance what you are trying to prove. Another standard method will allow you to find the answer without knowing it in advance:

Put $S = 1 + a + \ldots + a^n$.

Multiply by $a$:

$aS = a + \ldots + a^n + a^{n+1}$.

Now subtract the second equation from the first and note that most of the terms on the right hand side cancel:

$S(1-a) = S-aS = 1 - a^{n+1}$.

Since $a \neq 1$, $1-a \neq 0$ so we can divide both sides by it. Behold, we have gotten the answer

$S = \frac{1-a^{n+1}}{1-a}$

that we previously had to know in order to do a proof by induction.

share|improve this answer

If you multiply $s_n:=1+q+q^2+\ldots + q^n$ with $q$ you get $q+q^2+\ldots +q^n+q^{n+1}$, which differs from $a_n$ by only dropping the first and adding a new last term. More procisely, we find $qs_n=s_n-1+q^{n+1}$, hence (if $q\ne 1$) $$s_n=\frac{q^{n+1}-1}{q-1}=\frac1{1-q}+\frac1{q-1}\cdot q^{n+1}.$$ In your case, you have $q=\frac14$, so the first summand is $\frac43$ and the second tends to $0$ as $n\to\infty$.

share|improve this answer

I'm not really sure if it is possible to prove this using induction but we can do something else.

The sum $\displaystyle 1 + \frac{1}{4} + \frac{1}{4^2} + \cdots \frac{1}{4^k}$ can be written as $\displaystyle\sum_{n=0}^k \frac{1}{4^n}$. Now $\displaystyle\sum_{n=0}^k \displaystyle\frac{1}{4^n} = \frac{1-\frac{1}{4^{k+1}}}{1-\frac{1}{4}}$. Now letting $k \rightarrow \infty$ allows us to conclude that $\displaystyle 1 + \frac{1}{4} + \frac{1}{4^2} + \cdots \frac{1}{4^k} \rightarrow \displaystyle\frac{4}{3}$

share|improve this answer
    
Oops, sorry, fixed my mistake –  User Zero May 5 '13 at 20:50
    
I've deleted that comment. What you've got now is better, but still in error. You're saying a sum of finitely many terms is equal to a sum of infinitely many terms. –  Michael Hardy May 5 '13 at 22:38
  1. Induction is used to prove statements are true for all natural numbers.

  2. You want to prove that this is true only for infinitely large n.

That said, it should be clear that a mathematical induction is inapplicable here.

Trying to use induction to solve this problem is like trying to eat a soup with a fork.

share|improve this answer
    
Good points, but this doesn't actually answer the question (admittedly, the question is unanswerable!) so perhaps would be better off as a comment. –  Tom Oldfield May 5 '13 at 20:31
3  
One can demonstrate the value of the sum of the first $n$ terms by induction, and then take a limit as the number of terms grows. –  Michael Hardy May 5 '13 at 20:46

If you represent 4/3 using binary notation, you get:

1.0101.... (I don't know how to do a 'bar' to show repeating.)

The first 1 after the decimal is read as 1/4 the zero is in the 1/8 place, the next 1 is 1/16, etc. This reads as matching your infinite series.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.