Induction proof of $sum_i=0^n(5i+3) = fracn(5n+11)2+3$ for every natural $n$Factorial (Proof by Induction)Proving the Fibonacci identity $sum_i=1^n f_i^2=f_nf_n+1$ by inductionProof By Induction - $n^2 = sum_i=1 ^n (2i-1)$ for all $ngeq 1$Proof by contradiction and mathematical inductionWhat would be the induction hypothesis in my proof?Proof by Induction of an inequality with a sumIs my proof by induction on binary trees correct?Bogus Proof by Strong InductionProof By Induction: Summation of Polynomialtricky summation proof by induction
Is it legal to have the "// (c) 2019 John Smith" header in all files when there are hundreds of contributors?
Why doesn't a const reference extend the life of a temporary object passed via a function?
How to answer pointed "are you quitting" questioning when I don't want them to suspect
Calculate Levenshtein distance between two strings in Python
Information to fellow intern about hiring?
LM317 - Calculate dissipation due to voltage drop
What is GPS' 19 year rollover and does it present a cybersecurity issue?
Shall I use personal or official e-mail account when registering to external websites for work purpose?
How to move the player while also allowing forces to affect it
Wild Shape Centaur Into a Giant Elk: do their Charges stack?
How to deal with fear of taking dependencies
I see my dog run
Is domain driven design an anti-SQL pattern?
Is this homebrew feat, Beast of Burden, balanced?
Is Social Media Science Fiction?
Why do we use polarized capacitors?
Is this food a bread or a loaf?
Are objects structures and/or vice versa?
What kind of transistor turns on with 0.2 volts?
Latin words with no plurals in English
Are cabin dividers used to "hide" the flex of the airplane?
Patience, young "Padovan"
What do you call something that goes against the spirit of the law, but is legal when interpreting the law to the letter?
Can a planet have a different gravitational pull depending on its location in orbit around its sun?
Induction proof of $sum_i=0^n(5i+3) = fracn(5n+11)2+3$ for every natural $n$
Factorial (Proof by Induction)Proving the Fibonacci identity $sum_i=1^n f_i^2=f_nf_n+1$ by inductionProof By Induction - $n^2 = sum_i=1 ^n (2i-1)$ for all $ngeq 1$Proof by contradiction and mathematical inductionWhat would be the induction hypothesis in my proof?Proof by Induction of an inequality with a sumIs my proof by induction on binary trees correct?Bogus Proof by Strong InductionProof By Induction: Summation of Polynomialtricky summation proof by induction
$begingroup$
$$S_n = sum_i=0^n(5i+3)$$
I received a homework problem that instructed me to use induction to prove that for all natural numbers n
$$S_n = fracn(5n+11)2+3$$
First I proved that my base case of $S_0$ holds, because substituting $0$ for $n$ in both the top formula and the following formula makes both equal to $3$. The next step is to form my inductive hypothesis. My hypothesis is that
$$sum_i=0^n(5i+3) = fracn(5n+11)2+3$$ for all natural numbers $n$. Then I'm assuming that $$sum_i=0^k(5i+3) = frack(5k+11)2+3$$ holds when $n$ = some arbitrary natural number $k$ (I've since been told not to do $n=k$ for some reason).
Next step is to prove that $S_k+1$ holds, because if it does, knowing that my base case holds will tell me that $S_1$ holds, telling me that $S_2$ holds, etc.
To prove this, I took the equation from my assumption and substituted $k+1$ for $k$. Evaluating the left hand side of $frac(k+1)(5(k+1)+11)2+3$ eventually yielded $frac5k^2+21k+222$, and solving the right hand side of $sum_i=0^k+1(5i+3)$ using Gauss's(?) sum and splitting the terms of the sum (I don't know what to call it) to come to the same result. Since both sides of the equation reduced to the same expression, I reasoned that this proves that my original assumption holds, therefore the statement at the top has been proven.
I've gone wrong somewhere above, since I was told that I proved the original assertion with a direct proof rather than by induction. Where did I go wrong? I thought that after making my assumption and learning the case that needs to hold to make such assumption true, all I need to do is see if both sides of the equation equal each other. Has doing a direct proof of the original statement caused me to make too many assumptions? Or have I done something else inappropriate?
proof-verification summation induction alternative-proof
edited Apr 4 at 10:07
user21820
40.1k544162
asked Apr 4 at 0:12
user2709168user2709168
374
$endgroup$
add a comment |
$begingroup$
$$S_n = sum_i=0^n(5i+3)$$
I received a homework problem that instructed me to use induction to prove that for all natural numbers n
$$S_n = fracn(5n+11)2+3$$
First I proved that my base case of $S_0$ holds, because substituting $0$ for $n$ in both the top formula and the following formula makes both equal to $3$. The next step is to form my inductive hypothesis. My hypothesis is that
$$sum_i=0^n(5i+3) = fracn(5n+11)2+3$$ for all natural numbers $n$. Then I'm assuming that $$sum_i=0^k(5i+3) = frack(5k+11)2+3$$ holds when $n$ = some arbitrary natural number $k$ (I've since been told not to do $n=k$ for some reason).
Next step is to prove that $S_k+1$ holds, because if it does, knowing that my base case holds will tell me that $S_1$ holds, telling me that $S_2$ holds, etc.
To prove this, I took the equation from my assumption and substituted $k+1$ for $k$. Evaluating the left hand side of $frac(k+1)(5(k+1)+11)2+3$ eventually yielded $frac5k^2+21k+222$, and solving the right hand side of $sum_i=0^k+1(5i+3)$ using Gauss's(?) sum and splitting the terms of the sum (I don't know what to call it) to come to the same result. Since both sides of the equation reduced to the same expression, I reasoned that this proves that my original assumption holds, therefore the statement at the top has been proven.
I've gone wrong somewhere above, since I was told that I proved the original assertion with a direct proof rather than by induction. Where did I go wrong? I thought that after making my assumption and learning the case that needs to hold to make such assumption true, all I need to do is see if both sides of the equation equal each other. Has doing a direct proof of the original statement caused me to make too many assumptions? Or have I done something else inappropriate?
proof-verification summation induction alternative-proof
edited Apr 4 at 10:07
user21820
40.1k544162
asked Apr 4 at 0:12
user2709168user2709168
374
$endgroup$
$begingroup$
You were told... by whom? Your proof seems to line up with induction nicely.
$endgroup$
– abiessu
Apr 4 at 0:16
$begingroup$
@abiessu I was told this by my TA
$endgroup$
– user2709168
Apr 4 at 0:34
add a comment |
$begingroup$
$$S_n = sum_i=0^n(5i+3)$$
I received a homework problem that instructed me to use induction to prove that for all natural numbers n
$$S_n = fracn(5n+11)2+3$$
First I proved that my base case of $S_0$ holds, because substituting $0$ for $n$ in both the top formula and the following formula makes both equal to $3$. The next step is to form my inductive hypothesis. My hypothesis is that
$$sum_i=0^n(5i+3) = fracn(5n+11)2+3$$ for all natural numbers $n$. Then I'm assuming that $$sum_i=0^k(5i+3) = frack(5k+11)2+3$$ holds when $n$ = some arbitrary natural number $k$ (I've since been told not to do $n=k$ for some reason).
Next step is to prove that $S_k+1$ holds, because if it does, knowing that my base case holds will tell me that $S_1$ holds, telling me that $S_2$ holds, etc.
To prove this, I took the equation from my assumption and substituted $k+1$ for $k$. Evaluating the left hand side of $frac(k+1)(5(k+1)+11)2+3$ eventually yielded $frac5k^2+21k+222$, and solving the right hand side of $sum_i=0^k+1(5i+3)$ using Gauss's(?) sum and splitting the terms of the sum (I don't know what to call it) to come to the same result. Since both sides of the equation reduced to the same expression, I reasoned that this proves that my original assumption holds, therefore the statement at the top has been proven.
I've gone wrong somewhere above, since I was told that I proved the original assertion with a direct proof rather than by induction. Where did I go wrong? I thought that after making my assumption and learning the case that needs to hold to make such assumption true, all I need to do is see if both sides of the equation equal each other. Has doing a direct proof of the original statement caused me to make too many assumptions? Or have I done something else inappropriate?
proof-verification summation induction alternative-proof
edited Apr 4 at 10:07
user21820
40.1k544162
asked Apr 4 at 0:12
user2709168user2709168
374
$endgroup$
$$S_n = sum_i=0^n(5i+3)$$
I received a homework problem that instructed me to use induction to prove that for all natural numbers n
$$S_n = fracn(5n+11)2+3$$
First I proved that my base case of $S_0$ holds, because substituting $0$ for $n$ in both the top formula and the following formula makes both equal to $3$. The next step is to form my inductive hypothesis. My hypothesis is that
$$sum_i=0^n(5i+3) = fracn(5n+11)2+3$$ for all natural numbers $n$. Then I'm assuming that $$sum_i=0^k(5i+3) = frack(5k+11)2+3$$ holds when $n$ = some arbitrary natural number $k$ (I've since been told not to do $n=k$ for some reason).
Next step is to prove that $S_k+1$ holds, because if it does, knowing that my base case holds will tell me that $S_1$ holds, telling me that $S_2$ holds, etc.
To prove this, I took the equation from my assumption and substituted $k+1$ for $k$. Evaluating the left hand side of $frac(k+1)(5(k+1)+11)2+3$ eventually yielded $frac5k^2+21k+222$, and solving the right hand side of $sum_i=0^k+1(5i+3)$ using Gauss's(?) sum and splitting the terms of the sum (I don't know what to call it) to come to the same result. Since both sides of the equation reduced to the same expression, I reasoned that this proves that my original assumption holds, therefore the statement at the top has been proven.
I've gone wrong somewhere above, since I was told that I proved the original assertion with a direct proof rather than by induction. Where did I go wrong? I thought that after making my assumption and learning the case that needs to hold to make such assumption true, all I need to do is see if both sides of the equation equal each other. Has doing a direct proof of the original statement caused me to make too many assumptions? Or have I done something else inappropriate?
proof-verification summation induction alternative-proof
proof-verification summation induction alternative-proof
edited Apr 4 at 10:07
user21820
40.1k544162
asked Apr 4 at 0:12
user2709168user2709168
374
edited Apr 4 at 10:07
user21820
40.1k544162
asked Apr 4 at 0:12
user2709168user2709168
374
edited Apr 4 at 10:07
user21820
40.1k544162
edited Apr 4 at 10:07
user21820
40.1k544162
edited Apr 4 at 10:07
user21820
40.1k544162
40.1k544162
asked Apr 4 at 0:12
user2709168user2709168
374
asked Apr 4 at 0:12
user2709168user2709168
374
asked Apr 4 at 0:12
user2709168user2709168
374
374
$begingroup$
You were told... by whom? Your proof seems to line up with induction nicely.
$endgroup$
– abiessu
Apr 4 at 0:16
$begingroup$
@abiessu I was told this by my TA
$endgroup$
– user2709168
Apr 4 at 0:34
add a comment |
$begingroup$
You were told... by whom? Your proof seems to line up with induction nicely.
$endgroup$
– abiessu
Apr 4 at 0:16
$begingroup$
@abiessu I was told this by my TA
$endgroup$
– user2709168
Apr 4 at 0:34
$begingroup$
You were told... by whom? Your proof seems to line up with induction nicely.
$endgroup$
– abiessu
Apr 4 at 0:16
$begingroup$
You were told... by whom? Your proof seems to line up with induction nicely.
$endgroup$
– abiessu
Apr 4 at 0:16
$begingroup$
@abiessu I was told this by my TA
$endgroup$
– user2709168
Apr 4 at 0:34
$begingroup$
@abiessu I was told this by my TA
$endgroup$
– user2709168
Apr 4 at 0:34
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Typically, you want to remember that, for proof by induction, you have to make use of the induction assumption. You assume some case greater than your base case holds, and then show it implies the succeeding step - that gives you the whole "$S_1 implies S_2 implies S_3 implies ...$" chain.
So our assumption is
$$sum_i=0^k(5i+3) = frack(5k+11)2+3$$
We seek to show
$$sum_i=0^k+1(5i+3) = frac(k+1)(5(k+1)+11)2+3 = frac(k+1)(5k+16)2+3$$
Starting with the sum at the left, we can pull out the $(k+1)^th$ term:
$$sum_i=0^k+1(5i+3) = 5(k+1) + 3 + sum_i=0^k(5i+3) = 5k+8 + sum_i=0^k(5i+3)$$
As it happens, this new summation is precisely what we assume holds. So we substitute the corresponding expression and do some algebra:
$$beginalign
5k+9 + sum_i=0^k(5i+3) &= 5k+8 + frack(5k+11)2+3\
&=frac10k+16 + 5k^2 + 11k2 + 3\
&=frac5k^2+21k+162 + 3\
&= frac(k+1)(5k+16)2+3
endalign$$
Thus, the case for $(k+1)$ holds, completing the induction step.
answered Apr 4 at 0:24
Eevee TrainerEevee Trainer
10.1k31742
$endgroup$
$begingroup$
I think I mixed up my expressions in the post, but my intention was to have what you had as your assumption(?) as my inductive hypothesis. Do I not use that hypothesis when proving that the k+1 substitution holds?
$endgroup$
– user2709168
Apr 4 at 0:48
1
$begingroup$
You used something you refer to as "Gauss's (?) sum" in that, so, no, you did not make use of your induction hypothesis. At least in any obvious way because I have no idea what this sum you refer to is.
$endgroup$
– Eevee Trainer
Apr 4 at 0:54
$begingroup$
Are you saying my inductive hypothesis was Gauss's sum? Because that's not what I thought I was asserting Copy pasting a different comment of mine explaining what I meant: "I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2."
$endgroup$
– user2709168
Apr 4 at 0:56
1
$begingroup$
I'm saying that you're not making use of the inductive hypothesis. You verified the inductive step by another method, which makes no use of the inductive hypothesis. You have to assume the inductive hypothesis holds when you verify the inductive step: that's the whole point of the "this implies that implies that" domino effect. Alongside the base case and the fact that one implies the next - and you have to have a step implying the next, and have to show that implication holds - that gives us the domino effect. Verifying the induction step independently does not show $S_kimplies S_k+1$.
$endgroup$
– Eevee Trainer
Apr 4 at 1:04
$begingroup$
What is my inductive hypothesis in this situation? I thought the hypothesis was that the statement holds when n=k, therefore by proving it holds for k+1 then it holds for all n
$endgroup$
– user2709168
Apr 4 at 1:08
|
show 3 more comments
$begingroup$
I think the place where you say you used the "Gauss sum" is where your instructor says you just gave a direct proof. It's hard to tell, because you didn't show us your proof, you just said "and then I did and then ...".
What's expected is that you write the result for a particular value of $k$ - the inductive hypothesis, then add the next term and do some algebra to show that you get the result for $k+1$.
As an aside, I really don't like a question that asks you to prove something by induction when there is an easier straightforward way - in this case, Gauss's method.
answered Apr 4 at 0:20
Ethan BolkerEthan Bolker
45.8k553120
$endgroup$
$begingroup$
What do you mean by a particular value of k? I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2. I thought the particular value was writing that the statement holds when the value of k is n (or the other way around? trying to figure out what supposedly went wrong is confusing me), and then I can prove I get the same result for k+1.
$endgroup$
– user2709168
Apr 4 at 0:53
$begingroup$
I can't explain any better what I mean than what is in @EeveeTrainer 's answer and comments.
$endgroup$
– Ethan Bolker
Apr 4 at 1:19
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%2f3174030%2finduction-proof-of-sum-i-0n5i3-fracn5n1123-for-every-natur%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Typically, you want to remember that, for proof by induction, you have to make use of the induction assumption. You assume some case greater than your base case holds, and then show it implies the succeeding step - that gives you the whole "$S_1 implies S_2 implies S_3 implies ...$" chain.
So our assumption is
$$sum_i=0^k(5i+3) = frack(5k+11)2+3$$
We seek to show
$$sum_i=0^k+1(5i+3) = frac(k+1)(5(k+1)+11)2+3 = frac(k+1)(5k+16)2+3$$
Starting with the sum at the left, we can pull out the $(k+1)^th$ term:
$$sum_i=0^k+1(5i+3) = 5(k+1) + 3 + sum_i=0^k(5i+3) = 5k+8 + sum_i=0^k(5i+3)$$
As it happens, this new summation is precisely what we assume holds. So we substitute the corresponding expression and do some algebra:
$$beginalign
5k+9 + sum_i=0^k(5i+3) &= 5k+8 + frack(5k+11)2+3\
&=frac10k+16 + 5k^2 + 11k2 + 3\
&=frac5k^2+21k+162 + 3\
&= frac(k+1)(5k+16)2+3
endalign$$
Thus, the case for $(k+1)$ holds, completing the induction step.
answered Apr 4 at 0:24
Eevee TrainerEevee Trainer
10.1k31742
$endgroup$
$begingroup$
I think I mixed up my expressions in the post, but my intention was to have what you had as your assumption(?) as my inductive hypothesis. Do I not use that hypothesis when proving that the k+1 substitution holds?
$endgroup$
– user2709168
Apr 4 at 0:48
1
$begingroup$
You used something you refer to as "Gauss's (?) sum" in that, so, no, you did not make use of your induction hypothesis. At least in any obvious way because I have no idea what this sum you refer to is.
$endgroup$
– Eevee Trainer
Apr 4 at 0:54
$begingroup$
Are you saying my inductive hypothesis was Gauss's sum? Because that's not what I thought I was asserting Copy pasting a different comment of mine explaining what I meant: "I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2."
$endgroup$
– user2709168
Apr 4 at 0:56
1
$begingroup$
I'm saying that you're not making use of the inductive hypothesis. You verified the inductive step by another method, which makes no use of the inductive hypothesis. You have to assume the inductive hypothesis holds when you verify the inductive step: that's the whole point of the "this implies that implies that" domino effect. Alongside the base case and the fact that one implies the next - and you have to have a step implying the next, and have to show that implication holds - that gives us the domino effect. Verifying the induction step independently does not show $S_kimplies S_k+1$.
$endgroup$
– Eevee Trainer
Apr 4 at 1:04
$begingroup$
What is my inductive hypothesis in this situation? I thought the hypothesis was that the statement holds when n=k, therefore by proving it holds for k+1 then it holds for all n
$endgroup$
– user2709168
Apr 4 at 1:08
|
show 3 more comments
$begingroup$
Typically, you want to remember that, for proof by induction, you have to make use of the induction assumption. You assume some case greater than your base case holds, and then show it implies the succeeding step - that gives you the whole "$S_1 implies S_2 implies S_3 implies ...$" chain.
So our assumption is
$$sum_i=0^k(5i+3) = frack(5k+11)2+3$$
We seek to show
$$sum_i=0^k+1(5i+3) = frac(k+1)(5(k+1)+11)2+3 = frac(k+1)(5k+16)2+3$$
Starting with the sum at the left, we can pull out the $(k+1)^th$ term:
$$sum_i=0^k+1(5i+3) = 5(k+1) + 3 + sum_i=0^k(5i+3) = 5k+8 + sum_i=0^k(5i+3)$$
As it happens, this new summation is precisely what we assume holds. So we substitute the corresponding expression and do some algebra:
$$beginalign
5k+9 + sum_i=0^k(5i+3) &= 5k+8 + frack(5k+11)2+3\
&=frac10k+16 + 5k^2 + 11k2 + 3\
&=frac5k^2+21k+162 + 3\
&= frac(k+1)(5k+16)2+3
endalign$$
Thus, the case for $(k+1)$ holds, completing the induction step.
answered Apr 4 at 0:24
Eevee TrainerEevee Trainer
10.1k31742
$endgroup$
$begingroup$
I think I mixed up my expressions in the post, but my intention was to have what you had as your assumption(?) as my inductive hypothesis. Do I not use that hypothesis when proving that the k+1 substitution holds?
$endgroup$
– user2709168
Apr 4 at 0:48
1
$begingroup$
You used something you refer to as "Gauss's (?) sum" in that, so, no, you did not make use of your induction hypothesis. At least in any obvious way because I have no idea what this sum you refer to is.
$endgroup$
– Eevee Trainer
Apr 4 at 0:54
$begingroup$
Are you saying my inductive hypothesis was Gauss's sum? Because that's not what I thought I was asserting Copy pasting a different comment of mine explaining what I meant: "I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2."
$endgroup$
– user2709168
Apr 4 at 0:56
1
$begingroup$
I'm saying that you're not making use of the inductive hypothesis. You verified the inductive step by another method, which makes no use of the inductive hypothesis. You have to assume the inductive hypothesis holds when you verify the inductive step: that's the whole point of the "this implies that implies that" domino effect. Alongside the base case and the fact that one implies the next - and you have to have a step implying the next, and have to show that implication holds - that gives us the domino effect. Verifying the induction step independently does not show $S_kimplies S_k+1$.
$endgroup$
– Eevee Trainer
Apr 4 at 1:04
$begingroup$
What is my inductive hypothesis in this situation? I thought the hypothesis was that the statement holds when n=k, therefore by proving it holds for k+1 then it holds for all n
$endgroup$
– user2709168
Apr 4 at 1:08
|
show 3 more comments
$begingroup$
Typically, you want to remember that, for proof by induction, you have to make use of the induction assumption. You assume some case greater than your base case holds, and then show it implies the succeeding step - that gives you the whole "$S_1 implies S_2 implies S_3 implies ...$" chain.
So our assumption is
$$sum_i=0^k(5i+3) = frack(5k+11)2+3$$
We seek to show
$$sum_i=0^k+1(5i+3) = frac(k+1)(5(k+1)+11)2+3 = frac(k+1)(5k+16)2+3$$
Starting with the sum at the left, we can pull out the $(k+1)^th$ term:
$$sum_i=0^k+1(5i+3) = 5(k+1) + 3 + sum_i=0^k(5i+3) = 5k+8 + sum_i=0^k(5i+3)$$
As it happens, this new summation is precisely what we assume holds. So we substitute the corresponding expression and do some algebra:
$$beginalign
5k+9 + sum_i=0^k(5i+3) &= 5k+8 + frack(5k+11)2+3\
&=frac10k+16 + 5k^2 + 11k2 + 3\
&=frac5k^2+21k+162 + 3\
&= frac(k+1)(5k+16)2+3
endalign$$
Thus, the case for $(k+1)$ holds, completing the induction step.
answered Apr 4 at 0:24
Eevee TrainerEevee Trainer
10.1k31742
$endgroup$
Typically, you want to remember that, for proof by induction, you have to make use of the induction assumption. You assume some case greater than your base case holds, and then show it implies the succeeding step - that gives you the whole "$S_1 implies S_2 implies S_3 implies ...$" chain.
So our assumption is
$$sum_i=0^k(5i+3) = frack(5k+11)2+3$$
We seek to show
$$sum_i=0^k+1(5i+3) = frac(k+1)(5(k+1)+11)2+3 = frac(k+1)(5k+16)2+3$$
Starting with the sum at the left, we can pull out the $(k+1)^th$ term:
$$sum_i=0^k+1(5i+3) = 5(k+1) + 3 + sum_i=0^k(5i+3) = 5k+8 + sum_i=0^k(5i+3)$$
As it happens, this new summation is precisely what we assume holds. So we substitute the corresponding expression and do some algebra:
$$beginalign
5k+9 + sum_i=0^k(5i+3) &= 5k+8 + frack(5k+11)2+3\
&=frac10k+16 + 5k^2 + 11k2 + 3\
&=frac5k^2+21k+162 + 3\
&= frac(k+1)(5k+16)2+3
endalign$$
Thus, the case for $(k+1)$ holds, completing the induction step.
answered Apr 4 at 0:24
Eevee TrainerEevee Trainer
10.1k31742
answered Apr 4 at 0:24
Eevee TrainerEevee Trainer
10.1k31742
answered Apr 4 at 0:24
Eevee TrainerEevee Trainer
10.1k31742
answered Apr 4 at 0:24
Eevee TrainerEevee Trainer
10.1k31742
10.1k31742
$begingroup$
I think I mixed up my expressions in the post, but my intention was to have what you had as your assumption(?) as my inductive hypothesis. Do I not use that hypothesis when proving that the k+1 substitution holds?
$endgroup$
– user2709168
Apr 4 at 0:48
1
$begingroup$
You used something you refer to as "Gauss's (?) sum" in that, so, no, you did not make use of your induction hypothesis. At least in any obvious way because I have no idea what this sum you refer to is.
$endgroup$
– Eevee Trainer
Apr 4 at 0:54
$begingroup$
Are you saying my inductive hypothesis was Gauss's sum? Because that's not what I thought I was asserting Copy pasting a different comment of mine explaining what I meant: "I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2."
$endgroup$
– user2709168
Apr 4 at 0:56
1
$begingroup$
I'm saying that you're not making use of the inductive hypothesis. You verified the inductive step by another method, which makes no use of the inductive hypothesis. You have to assume the inductive hypothesis holds when you verify the inductive step: that's the whole point of the "this implies that implies that" domino effect. Alongside the base case and the fact that one implies the next - and you have to have a step implying the next, and have to show that implication holds - that gives us the domino effect. Verifying the induction step independently does not show $S_kimplies S_k+1$.
$endgroup$
– Eevee Trainer
Apr 4 at 1:04
$begingroup$
What is my inductive hypothesis in this situation? I thought the hypothesis was that the statement holds when n=k, therefore by proving it holds for k+1 then it holds for all n
$endgroup$
– user2709168
Apr 4 at 1:08
|
show 3 more comments
$begingroup$
I think I mixed up my expressions in the post, but my intention was to have what you had as your assumption(?) as my inductive hypothesis. Do I not use that hypothesis when proving that the k+1 substitution holds?
$endgroup$
– user2709168
Apr 4 at 0:48
1
$begingroup$
You used something you refer to as "Gauss's (?) sum" in that, so, no, you did not make use of your induction hypothesis. At least in any obvious way because I have no idea what this sum you refer to is.
$endgroup$
– Eevee Trainer
Apr 4 at 0:54
$begingroup$
Are you saying my inductive hypothesis was Gauss's sum? Because that's not what I thought I was asserting Copy pasting a different comment of mine explaining what I meant: "I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2."
$endgroup$
– user2709168
Apr 4 at 0:56
1
$begingroup$
I'm saying that you're not making use of the inductive hypothesis. You verified the inductive step by another method, which makes no use of the inductive hypothesis. You have to assume the inductive hypothesis holds when you verify the inductive step: that's the whole point of the "this implies that implies that" domino effect. Alongside the base case and the fact that one implies the next - and you have to have a step implying the next, and have to show that implication holds - that gives us the domino effect. Verifying the induction step independently does not show $S_kimplies S_k+1$.
$endgroup$
– Eevee Trainer
Apr 4 at 1:04
$begingroup$
What is my inductive hypothesis in this situation? I thought the hypothesis was that the statement holds when n=k, therefore by proving it holds for k+1 then it holds for all n
$endgroup$
– user2709168
Apr 4 at 1:08
$begingroup$
I think I mixed up my expressions in the post, but my intention was to have what you had as your assumption(?) as my inductive hypothesis. Do I not use that hypothesis when proving that the k+1 substitution holds?
$endgroup$
– user2709168
Apr 4 at 0:48
$begingroup$
I think I mixed up my expressions in the post, but my intention was to have what you had as your assumption(?) as my inductive hypothesis. Do I not use that hypothesis when proving that the k+1 substitution holds?
$endgroup$
– user2709168
Apr 4 at 0:48
1
1
$begingroup$
You used something you refer to as "Gauss's (?) sum" in that, so, no, you did not make use of your induction hypothesis. At least in any obvious way because I have no idea what this sum you refer to is.
$endgroup$
– Eevee Trainer
Apr 4 at 0:54
$begingroup$
You used something you refer to as "Gauss's (?) sum" in that, so, no, you did not make use of your induction hypothesis. At least in any obvious way because I have no idea what this sum you refer to is.
$endgroup$
– Eevee Trainer
Apr 4 at 0:54
$begingroup$
Are you saying my inductive hypothesis was Gauss's sum? Because that's not what I thought I was asserting Copy pasting a different comment of mine explaining what I meant: "I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2."
$endgroup$
– user2709168
Apr 4 at 0:56
$begingroup$
Are you saying my inductive hypothesis was Gauss's sum? Because that's not what I thought I was asserting Copy pasting a different comment of mine explaining what I meant: "I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2."
$endgroup$
– user2709168
Apr 4 at 0:56
1
1
$begingroup$
I'm saying that you're not making use of the inductive hypothesis. You verified the inductive step by another method, which makes no use of the inductive hypothesis. You have to assume the inductive hypothesis holds when you verify the inductive step: that's the whole point of the "this implies that implies that" domino effect. Alongside the base case and the fact that one implies the next - and you have to have a step implying the next, and have to show that implication holds - that gives us the domino effect. Verifying the induction step independently does not show $S_kimplies S_k+1$.
$endgroup$
– Eevee Trainer
Apr 4 at 1:04
$begingroup$
I'm saying that you're not making use of the inductive hypothesis. You verified the inductive step by another method, which makes no use of the inductive hypothesis. You have to assume the inductive hypothesis holds when you verify the inductive step: that's the whole point of the "this implies that implies that" domino effect. Alongside the base case and the fact that one implies the next - and you have to have a step implying the next, and have to show that implication holds - that gives us the domino effect. Verifying the induction step independently does not show $S_kimplies S_k+1$.
$endgroup$
– Eevee Trainer
Apr 4 at 1:04
$begingroup$
What is my inductive hypothesis in this situation? I thought the hypothesis was that the statement holds when n=k, therefore by proving it holds for k+1 then it holds for all n
$endgroup$
– user2709168
Apr 4 at 1:08
$begingroup$
What is my inductive hypothesis in this situation? I thought the hypothesis was that the statement holds when n=k, therefore by proving it holds for k+1 then it holds for all n
$endgroup$
– user2709168
Apr 4 at 1:08
|
show 3 more comments
$begingroup$
I think the place where you say you used the "Gauss sum" is where your instructor says you just gave a direct proof. It's hard to tell, because you didn't show us your proof, you just said "and then I did and then ...".
What's expected is that you write the result for a particular value of $k$ - the inductive hypothesis, then add the next term and do some algebra to show that you get the result for $k+1$.
As an aside, I really don't like a question that asks you to prove something by induction when there is an easier straightforward way - in this case, Gauss's method.
answered Apr 4 at 0:20
Ethan BolkerEthan Bolker
45.8k553120
$endgroup$
$begingroup$
What do you mean by a particular value of k? I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2. I thought the particular value was writing that the statement holds when the value of k is n (or the other way around? trying to figure out what supposedly went wrong is confusing me), and then I can prove I get the same result for k+1.
$endgroup$
– user2709168
Apr 4 at 0:53
$begingroup$
I can't explain any better what I mean than what is in @EeveeTrainer 's answer and comments.
$endgroup$
– Ethan Bolker
Apr 4 at 1:19
add a comment |
$begingroup$
I think the place where you say you used the "Gauss sum" is where your instructor says you just gave a direct proof. It's hard to tell, because you didn't show us your proof, you just said "and then I did and then ...".
What's expected is that you write the result for a particular value of $k$ - the inductive hypothesis, then add the next term and do some algebra to show that you get the result for $k+1$.
As an aside, I really don't like a question that asks you to prove something by induction when there is an easier straightforward way - in this case, Gauss's method.
answered Apr 4 at 0:20
Ethan BolkerEthan Bolker
45.8k553120
$endgroup$
$begingroup$
What do you mean by a particular value of k? I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2. I thought the particular value was writing that the statement holds when the value of k is n (or the other way around? trying to figure out what supposedly went wrong is confusing me), and then I can prove I get the same result for k+1.
$endgroup$
– user2709168
Apr 4 at 0:53
$begingroup$
I can't explain any better what I mean than what is in @EeveeTrainer 's answer and comments.
$endgroup$
– Ethan Bolker
Apr 4 at 1:19
add a comment |
$begingroup$
I think the place where you say you used the "Gauss sum" is where your instructor says you just gave a direct proof. It's hard to tell, because you didn't show us your proof, you just said "and then I did and then ...".
What's expected is that you write the result for a particular value of $k$ - the inductive hypothesis, then add the next term and do some algebra to show that you get the result for $k+1$.
As an aside, I really don't like a question that asks you to prove something by induction when there is an easier straightforward way - in this case, Gauss's method.
answered Apr 4 at 0:20
Ethan BolkerEthan Bolker
45.8k553120
$endgroup$
I think the place where you say you used the "Gauss sum" is where your instructor says you just gave a direct proof. It's hard to tell, because you didn't show us your proof, you just said "and then I did and then ...".
What's expected is that you write the result for a particular value of $k$ - the inductive hypothesis, then add the next term and do some algebra to show that you get the result for $k+1$.
As an aside, I really don't like a question that asks you to prove something by induction when there is an easier straightforward way - in this case, Gauss's method.
answered Apr 4 at 0:20
Ethan BolkerEthan Bolker
45.8k553120
answered Apr 4 at 0:20
Ethan BolkerEthan Bolker
45.8k553120
answered Apr 4 at 0:20
Ethan BolkerEthan Bolker
45.8k553120
answered Apr 4 at 0:20
Ethan BolkerEthan Bolker
45.8k553120
45.8k553120
$begingroup$
What do you mean by a particular value of k? I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2. I thought the particular value was writing that the statement holds when the value of k is n (or the other way around? trying to figure out what supposedly went wrong is confusing me), and then I can prove I get the same result for k+1.
$endgroup$
– user2709168
Apr 4 at 0:53
$begingroup$
I can't explain any better what I mean than what is in @EeveeTrainer 's answer and comments.
$endgroup$
– Ethan Bolker
Apr 4 at 1:19
add a comment |
$begingroup$
What do you mean by a particular value of k? I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2. I thought the particular value was writing that the statement holds when the value of k is n (or the other way around? trying to figure out what supposedly went wrong is confusing me), and then I can prove I get the same result for k+1.
$endgroup$
– user2709168
Apr 4 at 0:53
$begingroup$
I can't explain any better what I mean than what is in @EeveeTrainer 's answer and comments.
$endgroup$
– Ethan Bolker
Apr 4 at 1:19
$begingroup$
What do you mean by a particular value of k? I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2. I thought the particular value was writing that the statement holds when the value of k is n (or the other way around? trying to figure out what supposedly went wrong is confusing me), and then I can prove I get the same result for k+1.
$endgroup$
– user2709168
Apr 4 at 0:53
$begingroup$
What do you mean by a particular value of k? I mentioned Gauss's sum because that's one of the things I used to evaluate the right side of my equation- through turning the sum of 5i into 5((k+1)(k+2))/2. I thought the particular value was writing that the statement holds when the value of k is n (or the other way around? trying to figure out what supposedly went wrong is confusing me), and then I can prove I get the same result for k+1.
$endgroup$
– user2709168
Apr 4 at 0:53
$begingroup$
I can't explain any better what I mean than what is in @EeveeTrainer 's answer and comments.
$endgroup$
– Ethan Bolker
Apr 4 at 1:19
$begingroup$
I can't explain any better what I mean than what is in @EeveeTrainer 's answer and comments.
$endgroup$
– Ethan Bolker
Apr 4 at 1:19
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.
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%2f3174030%2finduction-proof-of-sum-i-0n5i3-fracn5n1123-for-every-natur%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
$begingroup$
You were told... by whom? Your proof seems to line up with induction nicely.
$endgroup$
– abiessu
Apr 4 at 0:16
$begingroup$
@abiessu I was told this by my TA
$endgroup$
– user2709168
Apr 4 at 0:34