Proving the geometric series $sum_i=0^n r^i = frac1-r^n+11-r$ by induction for $ngeq 1$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let $P(n)$ be the statement
$$
P(n) : sumlimits^n_i=0r^i = dfrac1-r^1+n1-rtext for all n in mathbbNtext.
$$
I am stuck at the base case:
$$P(1):1 + r = dfrac1-r^21-rtext.$$
I am stuck as to how I can show $P(1)$ is true.
proof-writing induction
 |Â
show 1 more comment
up vote
1
down vote
favorite
Let $P(n)$ be the statement
$$
P(n) : sumlimits^n_i=0r^i = dfrac1-r^1+n1-rtext for all n in mathbbNtext.
$$
I am stuck at the base case:
$$P(1):1 + r = dfrac1-r^21-rtext.$$
I am stuck as to how I can show $P(1)$ is true.
proof-writing induction
3
Hint: $a^2-b^2=(a+b)(a-b)$
â user105475
Aug 14 '14 at 1:42
Base Case is P(0) not P(1)
â user137481
Aug 14 '14 at 1:42
@user137481 Natural Numbers start at 1 ... so should the base case not be P(1)
â Guest
Aug 14 '14 at 1:43
1
That depends on your teacher. In some courses, Natural Numbers start at 0
â user137481
Aug 14 '14 at 1:47
1
Note that the problem really should have specified that $rne 1$. As to the base case, it depends on the exact statement of the problem. If we are asked to prove the result is true for every natural number $n$, then the base case is $n=1$. If we are asked to prove the result holds for every non-negative integer, then the base case is $n=0$.
â André Nicolas
Aug 14 '14 at 1:48
 |Â
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let $P(n)$ be the statement
$$
P(n) : sumlimits^n_i=0r^i = dfrac1-r^1+n1-rtext for all n in mathbbNtext.
$$
I am stuck at the base case:
$$P(1):1 + r = dfrac1-r^21-rtext.$$
I am stuck as to how I can show $P(1)$ is true.
proof-writing induction
Let $P(n)$ be the statement
$$
P(n) : sumlimits^n_i=0r^i = dfrac1-r^1+n1-rtext for all n in mathbbNtext.
$$
I am stuck at the base case:
$$P(1):1 + r = dfrac1-r^21-rtext.$$
I am stuck as to how I can show $P(1)$ is true.
proof-writing induction
proof-writing induction
edited Mar 23 '15 at 16:36
Daniel W. Farlow
17.3k114187
17.3k114187
asked Aug 14 '14 at 1:40
Guest
17311
17311
3
Hint: $a^2-b^2=(a+b)(a-b)$
â user105475
Aug 14 '14 at 1:42
Base Case is P(0) not P(1)
â user137481
Aug 14 '14 at 1:42
@user137481 Natural Numbers start at 1 ... so should the base case not be P(1)
â Guest
Aug 14 '14 at 1:43
1
That depends on your teacher. In some courses, Natural Numbers start at 0
â user137481
Aug 14 '14 at 1:47
1
Note that the problem really should have specified that $rne 1$. As to the base case, it depends on the exact statement of the problem. If we are asked to prove the result is true for every natural number $n$, then the base case is $n=1$. If we are asked to prove the result holds for every non-negative integer, then the base case is $n=0$.
â André Nicolas
Aug 14 '14 at 1:48
 |Â
show 1 more comment
3
Hint: $a^2-b^2=(a+b)(a-b)$
â user105475
Aug 14 '14 at 1:42
Base Case is P(0) not P(1)
â user137481
Aug 14 '14 at 1:42
@user137481 Natural Numbers start at 1 ... so should the base case not be P(1)
â Guest
Aug 14 '14 at 1:43
1
That depends on your teacher. In some courses, Natural Numbers start at 0
â user137481
Aug 14 '14 at 1:47
1
Note that the problem really should have specified that $rne 1$. As to the base case, it depends on the exact statement of the problem. If we are asked to prove the result is true for every natural number $n$, then the base case is $n=1$. If we are asked to prove the result holds for every non-negative integer, then the base case is $n=0$.
â André Nicolas
Aug 14 '14 at 1:48
3
3
Hint: $a^2-b^2=(a+b)(a-b)$
â user105475
Aug 14 '14 at 1:42
Hint: $a^2-b^2=(a+b)(a-b)$
â user105475
Aug 14 '14 at 1:42
Base Case is P(0) not P(1)
â user137481
Aug 14 '14 at 1:42
Base Case is P(0) not P(1)
â user137481
Aug 14 '14 at 1:42
@user137481 Natural Numbers start at 1 ... so should the base case not be P(1)
â Guest
Aug 14 '14 at 1:43
@user137481 Natural Numbers start at 1 ... so should the base case not be P(1)
â Guest
Aug 14 '14 at 1:43
1
1
That depends on your teacher. In some courses, Natural Numbers start at 0
â user137481
Aug 14 '14 at 1:47
That depends on your teacher. In some courses, Natural Numbers start at 0
â user137481
Aug 14 '14 at 1:47
1
1
Note that the problem really should have specified that $rne 1$. As to the base case, it depends on the exact statement of the problem. If we are asked to prove the result is true for every natural number $n$, then the base case is $n=1$. If we are asked to prove the result holds for every non-negative integer, then the base case is $n=0$.
â André Nicolas
Aug 14 '14 at 1:48
Note that the problem really should have specified that $rne 1$. As to the base case, it depends on the exact statement of the problem. If we are asked to prove the result is true for every natural number $n$, then the base case is $n=1$. If we are asked to prove the result holds for every non-negative integer, then the base case is $n=0$.
â André Nicolas
Aug 14 '14 at 1:48
 |Â
show 1 more comment
2 Answers
2
active
oldest
votes
up vote
0
down vote
Note: First note that you are really summing the geometric series ($a,rinmathbbR, aneq 0, rneq 1$)
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1=afrac1-r^n+11-r
$$
with $a=1$. Let's tidy up the question wording just a little bit and then prove your claim.
Claim: Let $a$ and $r$ be real numbers with $aneq 0$ and $rneq 1$. Prove that for each integer $ngeq 1$ that
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1.
$$
Proof. Fix $rinmathbbR, rneq 1$, and let $S(n)$ denote the following statement for $ngeq 1$:
$$
S(n) : 1+r+r^2+cdots+r^n=fracr^n+1-1r-1.
$$
In order to solve this problem, it is sufficient for us to prove that $S(n)$ holds for each $ngeq 1$; that is, it suffices to consider only $a=1$. For $r=0$, we can see that $S(n)$ becomes $1=1$. Thus, assume that $rneq 0$ without loss of generality.
Base step ($n=1$): The statement $S(1)$ says that $1+r=fracr^2-1r-1$, which is true since $r^2-1=(r+1)(r-1)$ and $rneq 1$. [Also observe that you could begin the induction at $n=0$ because $S(0)$ simply says $1=fracr-1r-1$.]
Inductive step ($S(k)to S(k+1)$): Fix some $kgeq 1$ and suppose that $S(k)$ is true; that is, assume that
$$
S(k) : 1+r+r^2+cdots+r^k=fracr^k+1-1r-1
$$
is true. We must show that $S(k+1)$ follows where
$$
S(k+1) : 1+r+r^2+cdots+r^k+r^k+1=fracr^k+2-1r-1.
$$
Starting with the left-hand side of $S(k+1)$,
beginalign
textLHS &= colorred1+r+r^2+cdots+r^k+r^k+1tagby definition\[1em]
&= colorredfracr^k+1-1r-1+r^k+1tagby $S(k)$\[1em]
&= fracr^k+1-1r-1+fracr^k+1(r-1)r-1tagcommon denom.\[1em]
&= fracr^k+1-1+r^k+1(r-1)r-1tagcombine like terms\[1em]
&= fracr^k+1-1+r^k+2-r^k+1r-1tagexpand\[1em]
&= fracr^k+2-1r-1,tagsimplify
endalign
we see that the right-hand side of $S(k+1)$ follows. Thus, $S(k)to S(k+1)$, completing the inductive step.
By mathematical induction, for all $ngeq 1, S(n)$ holds true. $blacksquare$
Last note: There are many identities that use this main result. For example, a question was posed not long at all ago to prove that $sum_i=0^n 2^i=2^n+1-1$. One can easily set $r=2$ in what we just proved to see that this result is true.
add a comment |Â
up vote
-1
down vote
$$1+r=frac1-r^21-r$$should lead you to check if $$(1+r)(1-r)=1-r^2.$$
I don't need to tell you more.
Why this downvote ?
â Yves Daoust
Mar 23 '15 at 9:11
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Note: First note that you are really summing the geometric series ($a,rinmathbbR, aneq 0, rneq 1$)
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1=afrac1-r^n+11-r
$$
with $a=1$. Let's tidy up the question wording just a little bit and then prove your claim.
Claim: Let $a$ and $r$ be real numbers with $aneq 0$ and $rneq 1$. Prove that for each integer $ngeq 1$ that
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1.
$$
Proof. Fix $rinmathbbR, rneq 1$, and let $S(n)$ denote the following statement for $ngeq 1$:
$$
S(n) : 1+r+r^2+cdots+r^n=fracr^n+1-1r-1.
$$
In order to solve this problem, it is sufficient for us to prove that $S(n)$ holds for each $ngeq 1$; that is, it suffices to consider only $a=1$. For $r=0$, we can see that $S(n)$ becomes $1=1$. Thus, assume that $rneq 0$ without loss of generality.
Base step ($n=1$): The statement $S(1)$ says that $1+r=fracr^2-1r-1$, which is true since $r^2-1=(r+1)(r-1)$ and $rneq 1$. [Also observe that you could begin the induction at $n=0$ because $S(0)$ simply says $1=fracr-1r-1$.]
Inductive step ($S(k)to S(k+1)$): Fix some $kgeq 1$ and suppose that $S(k)$ is true; that is, assume that
$$
S(k) : 1+r+r^2+cdots+r^k=fracr^k+1-1r-1
$$
is true. We must show that $S(k+1)$ follows where
$$
S(k+1) : 1+r+r^2+cdots+r^k+r^k+1=fracr^k+2-1r-1.
$$
Starting with the left-hand side of $S(k+1)$,
beginalign
textLHS &= colorred1+r+r^2+cdots+r^k+r^k+1tagby definition\[1em]
&= colorredfracr^k+1-1r-1+r^k+1tagby $S(k)$\[1em]
&= fracr^k+1-1r-1+fracr^k+1(r-1)r-1tagcommon denom.\[1em]
&= fracr^k+1-1+r^k+1(r-1)r-1tagcombine like terms\[1em]
&= fracr^k+1-1+r^k+2-r^k+1r-1tagexpand\[1em]
&= fracr^k+2-1r-1,tagsimplify
endalign
we see that the right-hand side of $S(k+1)$ follows. Thus, $S(k)to S(k+1)$, completing the inductive step.
By mathematical induction, for all $ngeq 1, S(n)$ holds true. $blacksquare$
Last note: There are many identities that use this main result. For example, a question was posed not long at all ago to prove that $sum_i=0^n 2^i=2^n+1-1$. One can easily set $r=2$ in what we just proved to see that this result is true.
add a comment |Â
up vote
0
down vote
Note: First note that you are really summing the geometric series ($a,rinmathbbR, aneq 0, rneq 1$)
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1=afrac1-r^n+11-r
$$
with $a=1$. Let's tidy up the question wording just a little bit and then prove your claim.
Claim: Let $a$ and $r$ be real numbers with $aneq 0$ and $rneq 1$. Prove that for each integer $ngeq 1$ that
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1.
$$
Proof. Fix $rinmathbbR, rneq 1$, and let $S(n)$ denote the following statement for $ngeq 1$:
$$
S(n) : 1+r+r^2+cdots+r^n=fracr^n+1-1r-1.
$$
In order to solve this problem, it is sufficient for us to prove that $S(n)$ holds for each $ngeq 1$; that is, it suffices to consider only $a=1$. For $r=0$, we can see that $S(n)$ becomes $1=1$. Thus, assume that $rneq 0$ without loss of generality.
Base step ($n=1$): The statement $S(1)$ says that $1+r=fracr^2-1r-1$, which is true since $r^2-1=(r+1)(r-1)$ and $rneq 1$. [Also observe that you could begin the induction at $n=0$ because $S(0)$ simply says $1=fracr-1r-1$.]
Inductive step ($S(k)to S(k+1)$): Fix some $kgeq 1$ and suppose that $S(k)$ is true; that is, assume that
$$
S(k) : 1+r+r^2+cdots+r^k=fracr^k+1-1r-1
$$
is true. We must show that $S(k+1)$ follows where
$$
S(k+1) : 1+r+r^2+cdots+r^k+r^k+1=fracr^k+2-1r-1.
$$
Starting with the left-hand side of $S(k+1)$,
beginalign
textLHS &= colorred1+r+r^2+cdots+r^k+r^k+1tagby definition\[1em]
&= colorredfracr^k+1-1r-1+r^k+1tagby $S(k)$\[1em]
&= fracr^k+1-1r-1+fracr^k+1(r-1)r-1tagcommon denom.\[1em]
&= fracr^k+1-1+r^k+1(r-1)r-1tagcombine like terms\[1em]
&= fracr^k+1-1+r^k+2-r^k+1r-1tagexpand\[1em]
&= fracr^k+2-1r-1,tagsimplify
endalign
we see that the right-hand side of $S(k+1)$ follows. Thus, $S(k)to S(k+1)$, completing the inductive step.
By mathematical induction, for all $ngeq 1, S(n)$ holds true. $blacksquare$
Last note: There are many identities that use this main result. For example, a question was posed not long at all ago to prove that $sum_i=0^n 2^i=2^n+1-1$. One can easily set $r=2$ in what we just proved to see that this result is true.
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Note: First note that you are really summing the geometric series ($a,rinmathbbR, aneq 0, rneq 1$)
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1=afrac1-r^n+11-r
$$
with $a=1$. Let's tidy up the question wording just a little bit and then prove your claim.
Claim: Let $a$ and $r$ be real numbers with $aneq 0$ and $rneq 1$. Prove that for each integer $ngeq 1$ that
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1.
$$
Proof. Fix $rinmathbbR, rneq 1$, and let $S(n)$ denote the following statement for $ngeq 1$:
$$
S(n) : 1+r+r^2+cdots+r^n=fracr^n+1-1r-1.
$$
In order to solve this problem, it is sufficient for us to prove that $S(n)$ holds for each $ngeq 1$; that is, it suffices to consider only $a=1$. For $r=0$, we can see that $S(n)$ becomes $1=1$. Thus, assume that $rneq 0$ without loss of generality.
Base step ($n=1$): The statement $S(1)$ says that $1+r=fracr^2-1r-1$, which is true since $r^2-1=(r+1)(r-1)$ and $rneq 1$. [Also observe that you could begin the induction at $n=0$ because $S(0)$ simply says $1=fracr-1r-1$.]
Inductive step ($S(k)to S(k+1)$): Fix some $kgeq 1$ and suppose that $S(k)$ is true; that is, assume that
$$
S(k) : 1+r+r^2+cdots+r^k=fracr^k+1-1r-1
$$
is true. We must show that $S(k+1)$ follows where
$$
S(k+1) : 1+r+r^2+cdots+r^k+r^k+1=fracr^k+2-1r-1.
$$
Starting with the left-hand side of $S(k+1)$,
beginalign
textLHS &= colorred1+r+r^2+cdots+r^k+r^k+1tagby definition\[1em]
&= colorredfracr^k+1-1r-1+r^k+1tagby $S(k)$\[1em]
&= fracr^k+1-1r-1+fracr^k+1(r-1)r-1tagcommon denom.\[1em]
&= fracr^k+1-1+r^k+1(r-1)r-1tagcombine like terms\[1em]
&= fracr^k+1-1+r^k+2-r^k+1r-1tagexpand\[1em]
&= fracr^k+2-1r-1,tagsimplify
endalign
we see that the right-hand side of $S(k+1)$ follows. Thus, $S(k)to S(k+1)$, completing the inductive step.
By mathematical induction, for all $ngeq 1, S(n)$ holds true. $blacksquare$
Last note: There are many identities that use this main result. For example, a question was posed not long at all ago to prove that $sum_i=0^n 2^i=2^n+1-1$. One can easily set $r=2$ in what we just proved to see that this result is true.
Note: First note that you are really summing the geometric series ($a,rinmathbbR, aneq 0, rneq 1$)
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1=afrac1-r^n+11-r
$$
with $a=1$. Let's tidy up the question wording just a little bit and then prove your claim.
Claim: Let $a$ and $r$ be real numbers with $aneq 0$ and $rneq 1$. Prove that for each integer $ngeq 1$ that
$$
a+ar+ar^2+cdots+ar^n=afracr^n+1-1r-1.
$$
Proof. Fix $rinmathbbR, rneq 1$, and let $S(n)$ denote the following statement for $ngeq 1$:
$$
S(n) : 1+r+r^2+cdots+r^n=fracr^n+1-1r-1.
$$
In order to solve this problem, it is sufficient for us to prove that $S(n)$ holds for each $ngeq 1$; that is, it suffices to consider only $a=1$. For $r=0$, we can see that $S(n)$ becomes $1=1$. Thus, assume that $rneq 0$ without loss of generality.
Base step ($n=1$): The statement $S(1)$ says that $1+r=fracr^2-1r-1$, which is true since $r^2-1=(r+1)(r-1)$ and $rneq 1$. [Also observe that you could begin the induction at $n=0$ because $S(0)$ simply says $1=fracr-1r-1$.]
Inductive step ($S(k)to S(k+1)$): Fix some $kgeq 1$ and suppose that $S(k)$ is true; that is, assume that
$$
S(k) : 1+r+r^2+cdots+r^k=fracr^k+1-1r-1
$$
is true. We must show that $S(k+1)$ follows where
$$
S(k+1) : 1+r+r^2+cdots+r^k+r^k+1=fracr^k+2-1r-1.
$$
Starting with the left-hand side of $S(k+1)$,
beginalign
textLHS &= colorred1+r+r^2+cdots+r^k+r^k+1tagby definition\[1em]
&= colorredfracr^k+1-1r-1+r^k+1tagby $S(k)$\[1em]
&= fracr^k+1-1r-1+fracr^k+1(r-1)r-1tagcommon denom.\[1em]
&= fracr^k+1-1+r^k+1(r-1)r-1tagcombine like terms\[1em]
&= fracr^k+1-1+r^k+2-r^k+1r-1tagexpand\[1em]
&= fracr^k+2-1r-1,tagsimplify
endalign
we see that the right-hand side of $S(k+1)$ follows. Thus, $S(k)to S(k+1)$, completing the inductive step.
By mathematical induction, for all $ngeq 1, S(n)$ holds true. $blacksquare$
Last note: There are many identities that use this main result. For example, a question was posed not long at all ago to prove that $sum_i=0^n 2^i=2^n+1-1$. One can easily set $r=2$ in what we just proved to see that this result is true.
edited Apr 13 '17 at 12:19
Communityâ¦
1
1
answered Mar 23 '15 at 9:01
Daniel W. Farlow
17.3k114187
17.3k114187
add a comment |Â
add a comment |Â
up vote
-1
down vote
$$1+r=frac1-r^21-r$$should lead you to check if $$(1+r)(1-r)=1-r^2.$$
I don't need to tell you more.
Why this downvote ?
â Yves Daoust
Mar 23 '15 at 9:11
add a comment |Â
up vote
-1
down vote
$$1+r=frac1-r^21-r$$should lead you to check if $$(1+r)(1-r)=1-r^2.$$
I don't need to tell you more.
Why this downvote ?
â Yves Daoust
Mar 23 '15 at 9:11
add a comment |Â
up vote
-1
down vote
up vote
-1
down vote
$$1+r=frac1-r^21-r$$should lead you to check if $$(1+r)(1-r)=1-r^2.$$
I don't need to tell you more.
$$1+r=frac1-r^21-r$$should lead you to check if $$(1+r)(1-r)=1-r^2.$$
I don't need to tell you more.
answered Mar 23 '15 at 9:10
Yves Daoust
114k666209
114k666209
Why this downvote ?
â Yves Daoust
Mar 23 '15 at 9:11
add a comment |Â
Why this downvote ?
â Yves Daoust
Mar 23 '15 at 9:11
Why this downvote ?
â Yves Daoust
Mar 23 '15 at 9:11
Why this downvote ?
â Yves Daoust
Mar 23 '15 at 9:11
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f896832%2fproving-the-geometric-series-sum-i-0n-ri-frac1-rn11-r-by-induc%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
3
Hint: $a^2-b^2=(a+b)(a-b)$
â user105475
Aug 14 '14 at 1:42
Base Case is P(0) not P(1)
â user137481
Aug 14 '14 at 1:42
@user137481 Natural Numbers start at 1 ... so should the base case not be P(1)
â Guest
Aug 14 '14 at 1:43
1
That depends on your teacher. In some courses, Natural Numbers start at 0
â user137481
Aug 14 '14 at 1:47
1
Note that the problem really should have specified that $rne 1$. As to the base case, it depends on the exact statement of the problem. If we are asked to prove the result is true for every natural number $n$, then the base case is $n=1$. If we are asked to prove the result holds for every non-negative integer, then the base case is $n=0$.
â André Nicolas
Aug 14 '14 at 1:48