Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
Later 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.
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} $$
After subtracting $1$ this is equivalent to $\frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \cdots = \frac{1}{3}$. Behold:
Image taken from here.
The below image can easily be made into an inductive proof.
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$$
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}$
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.
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$.
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}$
Induction is used to prove statements are true for all natural numbers.
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.
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.
