Proof by Induction Question including Rational Numbers
up vote
3
down vote
favorite
I just recently covered 'rational numbers' in class and was assigned the following question to solve using induction for n
, so that for all $q in mathbb{Q}$ {1}:
$$sum_{k=0}^n q^k = frac{q^{n+1}-1}{q-1}$$
I am not entirely sure on where to start, since up to this point I've only done proofs by induction involving natural numbers only. I've thought about leaving the variable q
as it is, and doing
n = 1
then assuming statement is true for n, solve for n + 1
where $n in mathbb{N}$, but it leaves me with a dead end, since there are too many unknown variables involved.
I hope someone can help me with this question and explain to me what the best approach would be and why!
Thank you!!
induction rational-numbers
add a comment |
up vote
3
down vote
favorite
I just recently covered 'rational numbers' in class and was assigned the following question to solve using induction for n
, so that for all $q in mathbb{Q}$ {1}:
$$sum_{k=0}^n q^k = frac{q^{n+1}-1}{q-1}$$
I am not entirely sure on where to start, since up to this point I've only done proofs by induction involving natural numbers only. I've thought about leaving the variable q
as it is, and doing
n = 1
then assuming statement is true for n, solve for n + 1
where $n in mathbb{N}$, but it leaves me with a dead end, since there are too many unknown variables involved.
I hope someone can help me with this question and explain to me what the best approach would be and why!
Thank you!!
induction rational-numbers
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I just recently covered 'rational numbers' in class and was assigned the following question to solve using induction for n
, so that for all $q in mathbb{Q}$ {1}:
$$sum_{k=0}^n q^k = frac{q^{n+1}-1}{q-1}$$
I am not entirely sure on where to start, since up to this point I've only done proofs by induction involving natural numbers only. I've thought about leaving the variable q
as it is, and doing
n = 1
then assuming statement is true for n, solve for n + 1
where $n in mathbb{N}$, but it leaves me with a dead end, since there are too many unknown variables involved.
I hope someone can help me with this question and explain to me what the best approach would be and why!
Thank you!!
induction rational-numbers
I just recently covered 'rational numbers' in class and was assigned the following question to solve using induction for n
, so that for all $q in mathbb{Q}$ {1}:
$$sum_{k=0}^n q^k = frac{q^{n+1}-1}{q-1}$$
I am not entirely sure on where to start, since up to this point I've only done proofs by induction involving natural numbers only. I've thought about leaving the variable q
as it is, and doing
n = 1
then assuming statement is true for n, solve for n + 1
where $n in mathbb{N}$, but it leaves me with a dead end, since there are too many unknown variables involved.
I hope someone can help me with this question and explain to me what the best approach would be and why!
Thank you!!
induction rational-numbers
induction rational-numbers
asked Nov 28 at 21:18
Rikk
424
424
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
up vote
1
down vote
accepted
Your attempt is right! You do not have to change the $q$; leave it as it is and do the standard induction regarding to $n$.
Therefore lets start with our basis case $n=0$:
$$begin{align}
sum_{k=0}^0q^k&=frac{q^{0+1}-1}{q-1}\
1&=1
end{align}$$
Next consider the new values $n=m$ and $n=m+1$ which corresponde to the two equations
$$begin{align}
sum_{k=0}^{m}q^k&=frac{q^{m+1}-1}{q-1}\
sum_{k=0}^{m+1}q^k&=frac{q^{m+2}-1}{q-1}
end{align}$$
Here the first one is our assumption the second one our hypothesis. Howsoever lets split up the second sum as the following
$$sum_{k=0}^{m+1}q^k=underbrace{sum_{k=0}^{m}q^k}_{=text{assumption}}+q^{m+1}$$
As we can see the remaining sum equals our assumption. Therefore we can replace it by the given fraction from above. This yields to
$$sum_{k=0}^{m}q^k+q^{m+1}=frac{q^{m+1}-1}{q-1}+q^{m+1}=frac{q^{m+1}-1+q^{m+2}-q^{m+1}}{q-1}=frac{q^{m+2}-1}{q-1}$$
And thus we have shown that from our assumption the hypothesis follows and therefore we are done.
Thank you @mrtaurho! I'm glad my attempt was going in the right direction! But is there a formal reason for why the basis case is n = 0? Although, it is a fair step, considering n = 0 does work perfectly when looking at the statement.
– Rikk
Nov 28 at 21:40
@Rikk I general you try to find the smallest possible natural number for which it works out. In your case it is given that $ninmathbb N$ - or at least you assumed that it has to be so - and $n=0$ is the first possible value of this set. In case it does not works out for $0$, one may consider $n=1$ and so on. Take a look at this for an example where you cannot start by setting $n=0$.
– mrtaurho
Nov 28 at 21:43
Fair! I am so used to using n = 1, that I have forgotten about using 0 as the first possible value of natural numbers. Thank you a lot for your clarification, regardless!
– Rikk
Nov 28 at 21:46
No problem. I am happy that I could clear your doubts :)
– mrtaurho
Nov 28 at 21:47
add a comment |
up vote
0
down vote
Well ...
Write down that assertion when $n=1$ and verify that it's true.
Assume that it's true for some particular (unspecified) value of $n$. Write down what that tells you - I recommend doing that with an ellipsis
$$
1 + q + q^2 + cdots + q^n = ldots
$$
Then add $q^{n+1}$ and see if you can turn that into what you want.
Having said that, I wish you didn't have to use induction. It's much easier just expanding with the distributive law:
$$
(q-1)(1 + q + q^2 + cdots + q^n) .
$$
Induction should be saved for problems where it really helps.
add a comment |
up vote
0
down vote
Hint:
The set in which the arithmetic operations take place has no importance. You indeed have use induction on the exponent.
The simplest, from my point of vizw, would be to prove by induction the factorisation formula:
$$x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+dots+x+1).$$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3017722%2fproof-by-induction-question-including-rational-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Your attempt is right! You do not have to change the $q$; leave it as it is and do the standard induction regarding to $n$.
Therefore lets start with our basis case $n=0$:
$$begin{align}
sum_{k=0}^0q^k&=frac{q^{0+1}-1}{q-1}\
1&=1
end{align}$$
Next consider the new values $n=m$ and $n=m+1$ which corresponde to the two equations
$$begin{align}
sum_{k=0}^{m}q^k&=frac{q^{m+1}-1}{q-1}\
sum_{k=0}^{m+1}q^k&=frac{q^{m+2}-1}{q-1}
end{align}$$
Here the first one is our assumption the second one our hypothesis. Howsoever lets split up the second sum as the following
$$sum_{k=0}^{m+1}q^k=underbrace{sum_{k=0}^{m}q^k}_{=text{assumption}}+q^{m+1}$$
As we can see the remaining sum equals our assumption. Therefore we can replace it by the given fraction from above. This yields to
$$sum_{k=0}^{m}q^k+q^{m+1}=frac{q^{m+1}-1}{q-1}+q^{m+1}=frac{q^{m+1}-1+q^{m+2}-q^{m+1}}{q-1}=frac{q^{m+2}-1}{q-1}$$
And thus we have shown that from our assumption the hypothesis follows and therefore we are done.
Thank you @mrtaurho! I'm glad my attempt was going in the right direction! But is there a formal reason for why the basis case is n = 0? Although, it is a fair step, considering n = 0 does work perfectly when looking at the statement.
– Rikk
Nov 28 at 21:40
@Rikk I general you try to find the smallest possible natural number for which it works out. In your case it is given that $ninmathbb N$ - or at least you assumed that it has to be so - and $n=0$ is the first possible value of this set. In case it does not works out for $0$, one may consider $n=1$ and so on. Take a look at this for an example where you cannot start by setting $n=0$.
– mrtaurho
Nov 28 at 21:43
Fair! I am so used to using n = 1, that I have forgotten about using 0 as the first possible value of natural numbers. Thank you a lot for your clarification, regardless!
– Rikk
Nov 28 at 21:46
No problem. I am happy that I could clear your doubts :)
– mrtaurho
Nov 28 at 21:47
add a comment |
up vote
1
down vote
accepted
Your attempt is right! You do not have to change the $q$; leave it as it is and do the standard induction regarding to $n$.
Therefore lets start with our basis case $n=0$:
$$begin{align}
sum_{k=0}^0q^k&=frac{q^{0+1}-1}{q-1}\
1&=1
end{align}$$
Next consider the new values $n=m$ and $n=m+1$ which corresponde to the two equations
$$begin{align}
sum_{k=0}^{m}q^k&=frac{q^{m+1}-1}{q-1}\
sum_{k=0}^{m+1}q^k&=frac{q^{m+2}-1}{q-1}
end{align}$$
Here the first one is our assumption the second one our hypothesis. Howsoever lets split up the second sum as the following
$$sum_{k=0}^{m+1}q^k=underbrace{sum_{k=0}^{m}q^k}_{=text{assumption}}+q^{m+1}$$
As we can see the remaining sum equals our assumption. Therefore we can replace it by the given fraction from above. This yields to
$$sum_{k=0}^{m}q^k+q^{m+1}=frac{q^{m+1}-1}{q-1}+q^{m+1}=frac{q^{m+1}-1+q^{m+2}-q^{m+1}}{q-1}=frac{q^{m+2}-1}{q-1}$$
And thus we have shown that from our assumption the hypothesis follows and therefore we are done.
Thank you @mrtaurho! I'm glad my attempt was going in the right direction! But is there a formal reason for why the basis case is n = 0? Although, it is a fair step, considering n = 0 does work perfectly when looking at the statement.
– Rikk
Nov 28 at 21:40
@Rikk I general you try to find the smallest possible natural number for which it works out. In your case it is given that $ninmathbb N$ - or at least you assumed that it has to be so - and $n=0$ is the first possible value of this set. In case it does not works out for $0$, one may consider $n=1$ and so on. Take a look at this for an example where you cannot start by setting $n=0$.
– mrtaurho
Nov 28 at 21:43
Fair! I am so used to using n = 1, that I have forgotten about using 0 as the first possible value of natural numbers. Thank you a lot for your clarification, regardless!
– Rikk
Nov 28 at 21:46
No problem. I am happy that I could clear your doubts :)
– mrtaurho
Nov 28 at 21:47
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Your attempt is right! You do not have to change the $q$; leave it as it is and do the standard induction regarding to $n$.
Therefore lets start with our basis case $n=0$:
$$begin{align}
sum_{k=0}^0q^k&=frac{q^{0+1}-1}{q-1}\
1&=1
end{align}$$
Next consider the new values $n=m$ and $n=m+1$ which corresponde to the two equations
$$begin{align}
sum_{k=0}^{m}q^k&=frac{q^{m+1}-1}{q-1}\
sum_{k=0}^{m+1}q^k&=frac{q^{m+2}-1}{q-1}
end{align}$$
Here the first one is our assumption the second one our hypothesis. Howsoever lets split up the second sum as the following
$$sum_{k=0}^{m+1}q^k=underbrace{sum_{k=0}^{m}q^k}_{=text{assumption}}+q^{m+1}$$
As we can see the remaining sum equals our assumption. Therefore we can replace it by the given fraction from above. This yields to
$$sum_{k=0}^{m}q^k+q^{m+1}=frac{q^{m+1}-1}{q-1}+q^{m+1}=frac{q^{m+1}-1+q^{m+2}-q^{m+1}}{q-1}=frac{q^{m+2}-1}{q-1}$$
And thus we have shown that from our assumption the hypothesis follows and therefore we are done.
Your attempt is right! You do not have to change the $q$; leave it as it is and do the standard induction regarding to $n$.
Therefore lets start with our basis case $n=0$:
$$begin{align}
sum_{k=0}^0q^k&=frac{q^{0+1}-1}{q-1}\
1&=1
end{align}$$
Next consider the new values $n=m$ and $n=m+1$ which corresponde to the two equations
$$begin{align}
sum_{k=0}^{m}q^k&=frac{q^{m+1}-1}{q-1}\
sum_{k=0}^{m+1}q^k&=frac{q^{m+2}-1}{q-1}
end{align}$$
Here the first one is our assumption the second one our hypothesis. Howsoever lets split up the second sum as the following
$$sum_{k=0}^{m+1}q^k=underbrace{sum_{k=0}^{m}q^k}_{=text{assumption}}+q^{m+1}$$
As we can see the remaining sum equals our assumption. Therefore we can replace it by the given fraction from above. This yields to
$$sum_{k=0}^{m}q^k+q^{m+1}=frac{q^{m+1}-1}{q-1}+q^{m+1}=frac{q^{m+1}-1+q^{m+2}-q^{m+1}}{q-1}=frac{q^{m+2}-1}{q-1}$$
And thus we have shown that from our assumption the hypothesis follows and therefore we are done.
answered Nov 28 at 21:26
mrtaurho
3,0351930
3,0351930
Thank you @mrtaurho! I'm glad my attempt was going in the right direction! But is there a formal reason for why the basis case is n = 0? Although, it is a fair step, considering n = 0 does work perfectly when looking at the statement.
– Rikk
Nov 28 at 21:40
@Rikk I general you try to find the smallest possible natural number for which it works out. In your case it is given that $ninmathbb N$ - or at least you assumed that it has to be so - and $n=0$ is the first possible value of this set. In case it does not works out for $0$, one may consider $n=1$ and so on. Take a look at this for an example where you cannot start by setting $n=0$.
– mrtaurho
Nov 28 at 21:43
Fair! I am so used to using n = 1, that I have forgotten about using 0 as the first possible value of natural numbers. Thank you a lot for your clarification, regardless!
– Rikk
Nov 28 at 21:46
No problem. I am happy that I could clear your doubts :)
– mrtaurho
Nov 28 at 21:47
add a comment |
Thank you @mrtaurho! I'm glad my attempt was going in the right direction! But is there a formal reason for why the basis case is n = 0? Although, it is a fair step, considering n = 0 does work perfectly when looking at the statement.
– Rikk
Nov 28 at 21:40
@Rikk I general you try to find the smallest possible natural number for which it works out. In your case it is given that $ninmathbb N$ - or at least you assumed that it has to be so - and $n=0$ is the first possible value of this set. In case it does not works out for $0$, one may consider $n=1$ and so on. Take a look at this for an example where you cannot start by setting $n=0$.
– mrtaurho
Nov 28 at 21:43
Fair! I am so used to using n = 1, that I have forgotten about using 0 as the first possible value of natural numbers. Thank you a lot for your clarification, regardless!
– Rikk
Nov 28 at 21:46
No problem. I am happy that I could clear your doubts :)
– mrtaurho
Nov 28 at 21:47
Thank you @mrtaurho! I'm glad my attempt was going in the right direction! But is there a formal reason for why the basis case is n = 0? Although, it is a fair step, considering n = 0 does work perfectly when looking at the statement.
– Rikk
Nov 28 at 21:40
Thank you @mrtaurho! I'm glad my attempt was going in the right direction! But is there a formal reason for why the basis case is n = 0? Although, it is a fair step, considering n = 0 does work perfectly when looking at the statement.
– Rikk
Nov 28 at 21:40
@Rikk I general you try to find the smallest possible natural number for which it works out. In your case it is given that $ninmathbb N$ - or at least you assumed that it has to be so - and $n=0$ is the first possible value of this set. In case it does not works out for $0$, one may consider $n=1$ and so on. Take a look at this for an example where you cannot start by setting $n=0$.
– mrtaurho
Nov 28 at 21:43
@Rikk I general you try to find the smallest possible natural number for which it works out. In your case it is given that $ninmathbb N$ - or at least you assumed that it has to be so - and $n=0$ is the first possible value of this set. In case it does not works out for $0$, one may consider $n=1$ and so on. Take a look at this for an example where you cannot start by setting $n=0$.
– mrtaurho
Nov 28 at 21:43
Fair! I am so used to using n = 1, that I have forgotten about using 0 as the first possible value of natural numbers. Thank you a lot for your clarification, regardless!
– Rikk
Nov 28 at 21:46
Fair! I am so used to using n = 1, that I have forgotten about using 0 as the first possible value of natural numbers. Thank you a lot for your clarification, regardless!
– Rikk
Nov 28 at 21:46
No problem. I am happy that I could clear your doubts :)
– mrtaurho
Nov 28 at 21:47
No problem. I am happy that I could clear your doubts :)
– mrtaurho
Nov 28 at 21:47
add a comment |
up vote
0
down vote
Well ...
Write down that assertion when $n=1$ and verify that it's true.
Assume that it's true for some particular (unspecified) value of $n$. Write down what that tells you - I recommend doing that with an ellipsis
$$
1 + q + q^2 + cdots + q^n = ldots
$$
Then add $q^{n+1}$ and see if you can turn that into what you want.
Having said that, I wish you didn't have to use induction. It's much easier just expanding with the distributive law:
$$
(q-1)(1 + q + q^2 + cdots + q^n) .
$$
Induction should be saved for problems where it really helps.
add a comment |
up vote
0
down vote
Well ...
Write down that assertion when $n=1$ and verify that it's true.
Assume that it's true for some particular (unspecified) value of $n$. Write down what that tells you - I recommend doing that with an ellipsis
$$
1 + q + q^2 + cdots + q^n = ldots
$$
Then add $q^{n+1}$ and see if you can turn that into what you want.
Having said that, I wish you didn't have to use induction. It's much easier just expanding with the distributive law:
$$
(q-1)(1 + q + q^2 + cdots + q^n) .
$$
Induction should be saved for problems where it really helps.
add a comment |
up vote
0
down vote
up vote
0
down vote
Well ...
Write down that assertion when $n=1$ and verify that it's true.
Assume that it's true for some particular (unspecified) value of $n$. Write down what that tells you - I recommend doing that with an ellipsis
$$
1 + q + q^2 + cdots + q^n = ldots
$$
Then add $q^{n+1}$ and see if you can turn that into what you want.
Having said that, I wish you didn't have to use induction. It's much easier just expanding with the distributive law:
$$
(q-1)(1 + q + q^2 + cdots + q^n) .
$$
Induction should be saved for problems where it really helps.
Well ...
Write down that assertion when $n=1$ and verify that it's true.
Assume that it's true for some particular (unspecified) value of $n$. Write down what that tells you - I recommend doing that with an ellipsis
$$
1 + q + q^2 + cdots + q^n = ldots
$$
Then add $q^{n+1}$ and see if you can turn that into what you want.
Having said that, I wish you didn't have to use induction. It's much easier just expanding with the distributive law:
$$
(q-1)(1 + q + q^2 + cdots + q^n) .
$$
Induction should be saved for problems where it really helps.
answered Nov 28 at 21:25
Ethan Bolker
40.7k546108
40.7k546108
add a comment |
add a comment |
up vote
0
down vote
Hint:
The set in which the arithmetic operations take place has no importance. You indeed have use induction on the exponent.
The simplest, from my point of vizw, would be to prove by induction the factorisation formula:
$$x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+dots+x+1).$$
add a comment |
up vote
0
down vote
Hint:
The set in which the arithmetic operations take place has no importance. You indeed have use induction on the exponent.
The simplest, from my point of vizw, would be to prove by induction the factorisation formula:
$$x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+dots+x+1).$$
add a comment |
up vote
0
down vote
up vote
0
down vote
Hint:
The set in which the arithmetic operations take place has no importance. You indeed have use induction on the exponent.
The simplest, from my point of vizw, would be to prove by induction the factorisation formula:
$$x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+dots+x+1).$$
Hint:
The set in which the arithmetic operations take place has no importance. You indeed have use induction on the exponent.
The simplest, from my point of vizw, would be to prove by induction the factorisation formula:
$$x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+dots+x+1).$$
answered Nov 28 at 21:26
Bernard
117k637110
117k637110
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3017722%2fproof-by-induction-question-including-rational-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown