Please help me understand the following solutionWhat is the second principle of finite induction?(Inductive...
Am I a Rude Number?
What are the advantages of using `make` for small projects?
Why is working on the same position for more than 15 years not a red flag?
integral inequality of length of curve
Can pricing be copyrighted?
Can we use the stored gravitational potential energy of a building to produce power?
High pressure canisters of air as gun-less projectiles
Using only 1s, make 29 with the minimum number of digits
Do authors have to be politically correct in article-writing?
How experienced do I need to be to go on a photography workshop?
Knowing when to use pictures over words
How to acknowledge an embarrassing job interview, now that I work directly with the interviewer?
A starship is travelling at 0.9c and collides with a small rock. Will it leave a clean hole through, or will more happen?
Why avoid shared user accounts?
Avoiding morning and evening handshakes
Can I become debt free or should I file for bankruptcy? How do I manage my debt and finances?
Rear brake cable temporary fix possible?
What to do if authors don't respond to my serious concerns about their paper?
When does coming up with an idea constitute sufficient contribution for authorship?
How did the original light saber work?
1 0 1 0 1 0 1 0 1 0 1
What is better: yes / no radio, or simple checkbox?
What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?
Number of FLOP (Floating Point Operations) for exponentiation
Please help me understand the following solution
What is the second principle of finite induction?(Inductive Proofs) Show why one inductive hypothesis works, and the other does not.Proving Inequalities using InductionFrobenius coin problem, 5 and 9Practice Examples of Proofs by Induction, Direct/Indirect MethodWhat does the constant mean in Big O notation?Showing a sequence defined recursively is convergentProving that $n! leq 2*(frac{n}2)^n$Prove by Induction help please???Proof by Mathematical Induction for Inequality
$begingroup$
Prove by induction of n
$sumlimits_{k=1}^n frac k{k+1} leq n - frac1{n+1}$
begin{align}sum_1^{n+1}frac k{k+1}&leq n-frac 1{n+1}+frac{n+1}{n+2}\&=n-frac 1{n+1}+1-frac 1{n+2}\&=(n+1)-frac{2(n+2)-1}{(n+1)(n+2)}\&=(n+1)-frac 2{n+1}+frac 1{(n+1)(n+2)}\&leq (n+1)-frac 2{n+2}+frac 1{n+2}=(n+1)-frac 1{n+2}end{align}
Now I'm a beginner at induction, and couldn't follow this solution very well.I was hoping someone could help break down the steps and explain them.
Questions
- How the inequality works
Wouldn't
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1} $
become
$sum_1^{n+1}frac k{k+1} +frac{n+1}{n+2} leq n-frac 1{n+1}$
and then
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}-frac{n+1}{n+2} $
instead of
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2} $
- My largest issue with induction, is when the inequalities change like in the first and last step. I don't understand how that works. Any explanation, or good resources to help with my understanding of how the inequality changes when performing induction would be helpful.
discrete-mathematics induction
$endgroup$
add a comment |
$begingroup$
Prove by induction of n
$sumlimits_{k=1}^n frac k{k+1} leq n - frac1{n+1}$
begin{align}sum_1^{n+1}frac k{k+1}&leq n-frac 1{n+1}+frac{n+1}{n+2}\&=n-frac 1{n+1}+1-frac 1{n+2}\&=(n+1)-frac{2(n+2)-1}{(n+1)(n+2)}\&=(n+1)-frac 2{n+1}+frac 1{(n+1)(n+2)}\&leq (n+1)-frac 2{n+2}+frac 1{n+2}=(n+1)-frac 1{n+2}end{align}
Now I'm a beginner at induction, and couldn't follow this solution very well.I was hoping someone could help break down the steps and explain them.
Questions
- How the inequality works
Wouldn't
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1} $
become
$sum_1^{n+1}frac k{k+1} +frac{n+1}{n+2} leq n-frac 1{n+1}$
and then
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}-frac{n+1}{n+2} $
instead of
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2} $
- My largest issue with induction, is when the inequalities change like in the first and last step. I don't understand how that works. Any explanation, or good resources to help with my understanding of how the inequality changes when performing induction would be helpful.
discrete-mathematics induction
$endgroup$
add a comment |
$begingroup$
Prove by induction of n
$sumlimits_{k=1}^n frac k{k+1} leq n - frac1{n+1}$
begin{align}sum_1^{n+1}frac k{k+1}&leq n-frac 1{n+1}+frac{n+1}{n+2}\&=n-frac 1{n+1}+1-frac 1{n+2}\&=(n+1)-frac{2(n+2)-1}{(n+1)(n+2)}\&=(n+1)-frac 2{n+1}+frac 1{(n+1)(n+2)}\&leq (n+1)-frac 2{n+2}+frac 1{n+2}=(n+1)-frac 1{n+2}end{align}
Now I'm a beginner at induction, and couldn't follow this solution very well.I was hoping someone could help break down the steps and explain them.
Questions
- How the inequality works
Wouldn't
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1} $
become
$sum_1^{n+1}frac k{k+1} +frac{n+1}{n+2} leq n-frac 1{n+1}$
and then
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}-frac{n+1}{n+2} $
instead of
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2} $
- My largest issue with induction, is when the inequalities change like in the first and last step. I don't understand how that works. Any explanation, or good resources to help with my understanding of how the inequality changes when performing induction would be helpful.
discrete-mathematics induction
$endgroup$
Prove by induction of n
$sumlimits_{k=1}^n frac k{k+1} leq n - frac1{n+1}$
begin{align}sum_1^{n+1}frac k{k+1}&leq n-frac 1{n+1}+frac{n+1}{n+2}\&=n-frac 1{n+1}+1-frac 1{n+2}\&=(n+1)-frac{2(n+2)-1}{(n+1)(n+2)}\&=(n+1)-frac 2{n+1}+frac 1{(n+1)(n+2)}\&leq (n+1)-frac 2{n+2}+frac 1{n+2}=(n+1)-frac 1{n+2}end{align}
Now I'm a beginner at induction, and couldn't follow this solution very well.I was hoping someone could help break down the steps and explain them.
Questions
- How the inequality works
Wouldn't
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1} $
become
$sum_1^{n+1}frac k{k+1} +frac{n+1}{n+2} leq n-frac 1{n+1}$
and then
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}-frac{n+1}{n+2} $
instead of
$sum_1^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2} $
- My largest issue with induction, is when the inequalities change like in the first and last step. I don't understand how that works. Any explanation, or good resources to help with my understanding of how the inequality changes when performing induction would be helpful.
discrete-mathematics induction
discrete-mathematics induction
asked 2 hours ago
BrownieBrownie
997
997
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Remember that in induction proofs, we start by assuming that the claim we're trying to prove is true for $n$, and then conclude that it must also be true for $n + 1$. In this case, we start with the induction assumption
$$sum_{k = 1}^{n} frac{k}{k + 1} leq n - frac{1}{n + 1},$$
and want to end with the conclusion that $$sum_{k = 1}^{n + 1} frac{k}{k + 1} leq n + 1 - frac{1}{n + 2} .$$
Here's the argument written out in a bit more detail with commentary on each step.
begin{align*}
sum_{k = 1}^{n + 1} frac{k}{k + 1} & = frac{n + 1}{n + 2} + sum_{k = 1}^{n} frac{k}{k + 1} & textrm{ (just writing out the sum)} \
& leq frac{n + 1}{n + 2} + n - frac{1}{n + 1} & textrm{ (applying the induction hypothesis)} \
& = 1 - frac{1}{n + 2} + n - frac{1}{n + 1} & textrm{ (rewriting $frac{n+ 1}{n + 2}$ as $frac{n + 2 - 1}{n + 2} = 1 - frac{1}{n + 2}$)} \
& = n + 1 - frac{1}{n + 1} - frac{1}{n + 2} & textrm{ (regrouping)} \
& = n + 1 - frac{(n + 2) + (n + 1)}{(n + 2)(n + 1)} & textrm{ (combining fractions)} \
& = n + 1 - frac{2(n + 2) - 1}{(n + 1)(n + 2)} & textrm{ (regrouping the numerator)} \
& = n + 1 - frac{2(n + 2)}{(n + 1)(n + 2)} + frac{1}{(n + 1)(n + 2)} & textrm{ (breaking the fraction back apart)} \
& = n + 1 - frac{2}{n + 1} + frac{1}{(n + 1)(n + 2)} & textrm{ (simplifying the fraction)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{(n + 1)(n + 2)} & textrm{ (we slightly modified the second-to-last summand)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{n + 2} & textrm{ (modifying the last summand)} \
& = n + 1 - frac{1}{n + 2} & textrm{ (combining the fractions)} .
end{align*}
So in summary, we began with the assumption that the claim held for $n$, and through some arithmetic trickery concluded that it therefore held for $n + 1$.
$endgroup$
1
$begingroup$
This is an amazing break down, could explain your second-to-last and third-to-last steps where you modify the summand? Oh I think I might understand, is it to make the inequality <= ?
$endgroup$
– Brownie
1 hour ago
1
$begingroup$
@Brownie In the third-to-last step, we observe that $n + 1 leq n + 2$, so $frac{2}{n + 1} geq frac{2}{n + 2}$, so $- frac{2}{n + 1} leq - frac{2}{n + 2}$. For the second-to-last step, we can see that $frac{1}{n + 2} = frac{n + 1}{(n + 1)(n + 2)} = (n + 1) frac{1}{(n + 1)(n + 2)} geq frac{1}{(n + 1)(n + 2)}$.
$endgroup$
– AJY
1 hour ago
1
$begingroup$
So is this a step you saw you could implement to get the final equal to $ n + 1 - frac{1}{n + 2} $ ? Or is there something that would push you towards doing this?
$endgroup$
– Brownie
1 hour ago
2
$begingroup$
@Brownie The short answer is that these kinds of tricks come easier with practice. We wanted to get to a very particular estimate, and just kinda made what estimates we could until it fell out just right. Sometimes (often) it just takes trial and error.
$endgroup$
– AJY
1 hour ago
add a comment |
$begingroup$
Regarding the first inequality you're asking about, they are actually adding the term $frac{n+1}{n+2}$ to both sides, but on the left hand side it is added by increasing the upper limit in the sum by $1$, and to not change the inequality you have to add $frac{n+1}{n+2}$ to the right hand side.
The subsequent steps in the proof you posted are just rearrangements of fractions using algebra, nothing actually changes there until the last line. Then they just use the fact that $frac{1}{(n+1)(n+2)} leq frac{1}{n+2}$
$endgroup$
$begingroup$
Cool just last quick question, for the left hand side if instead of increasing the upper limit of the sum by 1, I added $frac{n+1}{n+2}$ to both sides, that would be the same?
$endgroup$
– Brownie
2 hours ago
$begingroup$
Yes, that would be the same.
$endgroup$
– Thomas Fjærvik
2 hours ago
add a comment |
$begingroup$
If $aleq b $, then $a+cleq b+c $ for any $cin Bbb R $. By assumption, we have $$sum_{k=1}^{n}frac k{k+1}leq n-frac 1{n+1}.$$ Now add $dfrac{n+1}{n+2}$ on both sides, i.e., $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$ Note that $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}=sum_{k=1}^{n+1}frac k{k+1}.$$ Hence we have $$sum_{k=1}^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$
$endgroup$
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%2f3133089%2fplease-help-me-understand-the-following-solution%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
$begingroup$
Remember that in induction proofs, we start by assuming that the claim we're trying to prove is true for $n$, and then conclude that it must also be true for $n + 1$. In this case, we start with the induction assumption
$$sum_{k = 1}^{n} frac{k}{k + 1} leq n - frac{1}{n + 1},$$
and want to end with the conclusion that $$sum_{k = 1}^{n + 1} frac{k}{k + 1} leq n + 1 - frac{1}{n + 2} .$$
Here's the argument written out in a bit more detail with commentary on each step.
begin{align*}
sum_{k = 1}^{n + 1} frac{k}{k + 1} & = frac{n + 1}{n + 2} + sum_{k = 1}^{n} frac{k}{k + 1} & textrm{ (just writing out the sum)} \
& leq frac{n + 1}{n + 2} + n - frac{1}{n + 1} & textrm{ (applying the induction hypothesis)} \
& = 1 - frac{1}{n + 2} + n - frac{1}{n + 1} & textrm{ (rewriting $frac{n+ 1}{n + 2}$ as $frac{n + 2 - 1}{n + 2} = 1 - frac{1}{n + 2}$)} \
& = n + 1 - frac{1}{n + 1} - frac{1}{n + 2} & textrm{ (regrouping)} \
& = n + 1 - frac{(n + 2) + (n + 1)}{(n + 2)(n + 1)} & textrm{ (combining fractions)} \
& = n + 1 - frac{2(n + 2) - 1}{(n + 1)(n + 2)} & textrm{ (regrouping the numerator)} \
& = n + 1 - frac{2(n + 2)}{(n + 1)(n + 2)} + frac{1}{(n + 1)(n + 2)} & textrm{ (breaking the fraction back apart)} \
& = n + 1 - frac{2}{n + 1} + frac{1}{(n + 1)(n + 2)} & textrm{ (simplifying the fraction)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{(n + 1)(n + 2)} & textrm{ (we slightly modified the second-to-last summand)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{n + 2} & textrm{ (modifying the last summand)} \
& = n + 1 - frac{1}{n + 2} & textrm{ (combining the fractions)} .
end{align*}
So in summary, we began with the assumption that the claim held for $n$, and through some arithmetic trickery concluded that it therefore held for $n + 1$.
$endgroup$
1
$begingroup$
This is an amazing break down, could explain your second-to-last and third-to-last steps where you modify the summand? Oh I think I might understand, is it to make the inequality <= ?
$endgroup$
– Brownie
1 hour ago
1
$begingroup$
@Brownie In the third-to-last step, we observe that $n + 1 leq n + 2$, so $frac{2}{n + 1} geq frac{2}{n + 2}$, so $- frac{2}{n + 1} leq - frac{2}{n + 2}$. For the second-to-last step, we can see that $frac{1}{n + 2} = frac{n + 1}{(n + 1)(n + 2)} = (n + 1) frac{1}{(n + 1)(n + 2)} geq frac{1}{(n + 1)(n + 2)}$.
$endgroup$
– AJY
1 hour ago
1
$begingroup$
So is this a step you saw you could implement to get the final equal to $ n + 1 - frac{1}{n + 2} $ ? Or is there something that would push you towards doing this?
$endgroup$
– Brownie
1 hour ago
2
$begingroup$
@Brownie The short answer is that these kinds of tricks come easier with practice. We wanted to get to a very particular estimate, and just kinda made what estimates we could until it fell out just right. Sometimes (often) it just takes trial and error.
$endgroup$
– AJY
1 hour ago
add a comment |
$begingroup$
Remember that in induction proofs, we start by assuming that the claim we're trying to prove is true for $n$, and then conclude that it must also be true for $n + 1$. In this case, we start with the induction assumption
$$sum_{k = 1}^{n} frac{k}{k + 1} leq n - frac{1}{n + 1},$$
and want to end with the conclusion that $$sum_{k = 1}^{n + 1} frac{k}{k + 1} leq n + 1 - frac{1}{n + 2} .$$
Here's the argument written out in a bit more detail with commentary on each step.
begin{align*}
sum_{k = 1}^{n + 1} frac{k}{k + 1} & = frac{n + 1}{n + 2} + sum_{k = 1}^{n} frac{k}{k + 1} & textrm{ (just writing out the sum)} \
& leq frac{n + 1}{n + 2} + n - frac{1}{n + 1} & textrm{ (applying the induction hypothesis)} \
& = 1 - frac{1}{n + 2} + n - frac{1}{n + 1} & textrm{ (rewriting $frac{n+ 1}{n + 2}$ as $frac{n + 2 - 1}{n + 2} = 1 - frac{1}{n + 2}$)} \
& = n + 1 - frac{1}{n + 1} - frac{1}{n + 2} & textrm{ (regrouping)} \
& = n + 1 - frac{(n + 2) + (n + 1)}{(n + 2)(n + 1)} & textrm{ (combining fractions)} \
& = n + 1 - frac{2(n + 2) - 1}{(n + 1)(n + 2)} & textrm{ (regrouping the numerator)} \
& = n + 1 - frac{2(n + 2)}{(n + 1)(n + 2)} + frac{1}{(n + 1)(n + 2)} & textrm{ (breaking the fraction back apart)} \
& = n + 1 - frac{2}{n + 1} + frac{1}{(n + 1)(n + 2)} & textrm{ (simplifying the fraction)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{(n + 1)(n + 2)} & textrm{ (we slightly modified the second-to-last summand)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{n + 2} & textrm{ (modifying the last summand)} \
& = n + 1 - frac{1}{n + 2} & textrm{ (combining the fractions)} .
end{align*}
So in summary, we began with the assumption that the claim held for $n$, and through some arithmetic trickery concluded that it therefore held for $n + 1$.
$endgroup$
1
$begingroup$
This is an amazing break down, could explain your second-to-last and third-to-last steps where you modify the summand? Oh I think I might understand, is it to make the inequality <= ?
$endgroup$
– Brownie
1 hour ago
1
$begingroup$
@Brownie In the third-to-last step, we observe that $n + 1 leq n + 2$, so $frac{2}{n + 1} geq frac{2}{n + 2}$, so $- frac{2}{n + 1} leq - frac{2}{n + 2}$. For the second-to-last step, we can see that $frac{1}{n + 2} = frac{n + 1}{(n + 1)(n + 2)} = (n + 1) frac{1}{(n + 1)(n + 2)} geq frac{1}{(n + 1)(n + 2)}$.
$endgroup$
– AJY
1 hour ago
1
$begingroup$
So is this a step you saw you could implement to get the final equal to $ n + 1 - frac{1}{n + 2} $ ? Or is there something that would push you towards doing this?
$endgroup$
– Brownie
1 hour ago
2
$begingroup$
@Brownie The short answer is that these kinds of tricks come easier with practice. We wanted to get to a very particular estimate, and just kinda made what estimates we could until it fell out just right. Sometimes (often) it just takes trial and error.
$endgroup$
– AJY
1 hour ago
add a comment |
$begingroup$
Remember that in induction proofs, we start by assuming that the claim we're trying to prove is true for $n$, and then conclude that it must also be true for $n + 1$. In this case, we start with the induction assumption
$$sum_{k = 1}^{n} frac{k}{k + 1} leq n - frac{1}{n + 1},$$
and want to end with the conclusion that $$sum_{k = 1}^{n + 1} frac{k}{k + 1} leq n + 1 - frac{1}{n + 2} .$$
Here's the argument written out in a bit more detail with commentary on each step.
begin{align*}
sum_{k = 1}^{n + 1} frac{k}{k + 1} & = frac{n + 1}{n + 2} + sum_{k = 1}^{n} frac{k}{k + 1} & textrm{ (just writing out the sum)} \
& leq frac{n + 1}{n + 2} + n - frac{1}{n + 1} & textrm{ (applying the induction hypothesis)} \
& = 1 - frac{1}{n + 2} + n - frac{1}{n + 1} & textrm{ (rewriting $frac{n+ 1}{n + 2}$ as $frac{n + 2 - 1}{n + 2} = 1 - frac{1}{n + 2}$)} \
& = n + 1 - frac{1}{n + 1} - frac{1}{n + 2} & textrm{ (regrouping)} \
& = n + 1 - frac{(n + 2) + (n + 1)}{(n + 2)(n + 1)} & textrm{ (combining fractions)} \
& = n + 1 - frac{2(n + 2) - 1}{(n + 1)(n + 2)} & textrm{ (regrouping the numerator)} \
& = n + 1 - frac{2(n + 2)}{(n + 1)(n + 2)} + frac{1}{(n + 1)(n + 2)} & textrm{ (breaking the fraction back apart)} \
& = n + 1 - frac{2}{n + 1} + frac{1}{(n + 1)(n + 2)} & textrm{ (simplifying the fraction)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{(n + 1)(n + 2)} & textrm{ (we slightly modified the second-to-last summand)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{n + 2} & textrm{ (modifying the last summand)} \
& = n + 1 - frac{1}{n + 2} & textrm{ (combining the fractions)} .
end{align*}
So in summary, we began with the assumption that the claim held for $n$, and through some arithmetic trickery concluded that it therefore held for $n + 1$.
$endgroup$
Remember that in induction proofs, we start by assuming that the claim we're trying to prove is true for $n$, and then conclude that it must also be true for $n + 1$. In this case, we start with the induction assumption
$$sum_{k = 1}^{n} frac{k}{k + 1} leq n - frac{1}{n + 1},$$
and want to end with the conclusion that $$sum_{k = 1}^{n + 1} frac{k}{k + 1} leq n + 1 - frac{1}{n + 2} .$$
Here's the argument written out in a bit more detail with commentary on each step.
begin{align*}
sum_{k = 1}^{n + 1} frac{k}{k + 1} & = frac{n + 1}{n + 2} + sum_{k = 1}^{n} frac{k}{k + 1} & textrm{ (just writing out the sum)} \
& leq frac{n + 1}{n + 2} + n - frac{1}{n + 1} & textrm{ (applying the induction hypothesis)} \
& = 1 - frac{1}{n + 2} + n - frac{1}{n + 1} & textrm{ (rewriting $frac{n+ 1}{n + 2}$ as $frac{n + 2 - 1}{n + 2} = 1 - frac{1}{n + 2}$)} \
& = n + 1 - frac{1}{n + 1} - frac{1}{n + 2} & textrm{ (regrouping)} \
& = n + 1 - frac{(n + 2) + (n + 1)}{(n + 2)(n + 1)} & textrm{ (combining fractions)} \
& = n + 1 - frac{2(n + 2) - 1}{(n + 1)(n + 2)} & textrm{ (regrouping the numerator)} \
& = n + 1 - frac{2(n + 2)}{(n + 1)(n + 2)} + frac{1}{(n + 1)(n + 2)} & textrm{ (breaking the fraction back apart)} \
& = n + 1 - frac{2}{n + 1} + frac{1}{(n + 1)(n + 2)} & textrm{ (simplifying the fraction)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{(n + 1)(n + 2)} & textrm{ (we slightly modified the second-to-last summand)} \
& leq n + 1 - frac{2}{n + 2} + frac{1}{n + 2} & textrm{ (modifying the last summand)} \
& = n + 1 - frac{1}{n + 2} & textrm{ (combining the fractions)} .
end{align*}
So in summary, we began with the assumption that the claim held for $n$, and through some arithmetic trickery concluded that it therefore held for $n + 1$.
edited 1 hour ago
answered 2 hours ago
AJYAJY
4,19521128
4,19521128
1
$begingroup$
This is an amazing break down, could explain your second-to-last and third-to-last steps where you modify the summand? Oh I think I might understand, is it to make the inequality <= ?
$endgroup$
– Brownie
1 hour ago
1
$begingroup$
@Brownie In the third-to-last step, we observe that $n + 1 leq n + 2$, so $frac{2}{n + 1} geq frac{2}{n + 2}$, so $- frac{2}{n + 1} leq - frac{2}{n + 2}$. For the second-to-last step, we can see that $frac{1}{n + 2} = frac{n + 1}{(n + 1)(n + 2)} = (n + 1) frac{1}{(n + 1)(n + 2)} geq frac{1}{(n + 1)(n + 2)}$.
$endgroup$
– AJY
1 hour ago
1
$begingroup$
So is this a step you saw you could implement to get the final equal to $ n + 1 - frac{1}{n + 2} $ ? Or is there something that would push you towards doing this?
$endgroup$
– Brownie
1 hour ago
2
$begingroup$
@Brownie The short answer is that these kinds of tricks come easier with practice. We wanted to get to a very particular estimate, and just kinda made what estimates we could until it fell out just right. Sometimes (often) it just takes trial and error.
$endgroup$
– AJY
1 hour ago
add a comment |
1
$begingroup$
This is an amazing break down, could explain your second-to-last and third-to-last steps where you modify the summand? Oh I think I might understand, is it to make the inequality <= ?
$endgroup$
– Brownie
1 hour ago
1
$begingroup$
@Brownie In the third-to-last step, we observe that $n + 1 leq n + 2$, so $frac{2}{n + 1} geq frac{2}{n + 2}$, so $- frac{2}{n + 1} leq - frac{2}{n + 2}$. For the second-to-last step, we can see that $frac{1}{n + 2} = frac{n + 1}{(n + 1)(n + 2)} = (n + 1) frac{1}{(n + 1)(n + 2)} geq frac{1}{(n + 1)(n + 2)}$.
$endgroup$
– AJY
1 hour ago
1
$begingroup$
So is this a step you saw you could implement to get the final equal to $ n + 1 - frac{1}{n + 2} $ ? Or is there something that would push you towards doing this?
$endgroup$
– Brownie
1 hour ago
2
$begingroup$
@Brownie The short answer is that these kinds of tricks come easier with practice. We wanted to get to a very particular estimate, and just kinda made what estimates we could until it fell out just right. Sometimes (often) it just takes trial and error.
$endgroup$
– AJY
1 hour ago
1
1
$begingroup$
This is an amazing break down, could explain your second-to-last and third-to-last steps where you modify the summand? Oh I think I might understand, is it to make the inequality <= ?
$endgroup$
– Brownie
1 hour ago
$begingroup$
This is an amazing break down, could explain your second-to-last and third-to-last steps where you modify the summand? Oh I think I might understand, is it to make the inequality <= ?
$endgroup$
– Brownie
1 hour ago
1
1
$begingroup$
@Brownie In the third-to-last step, we observe that $n + 1 leq n + 2$, so $frac{2}{n + 1} geq frac{2}{n + 2}$, so $- frac{2}{n + 1} leq - frac{2}{n + 2}$. For the second-to-last step, we can see that $frac{1}{n + 2} = frac{n + 1}{(n + 1)(n + 2)} = (n + 1) frac{1}{(n + 1)(n + 2)} geq frac{1}{(n + 1)(n + 2)}$.
$endgroup$
– AJY
1 hour ago
$begingroup$
@Brownie In the third-to-last step, we observe that $n + 1 leq n + 2$, so $frac{2}{n + 1} geq frac{2}{n + 2}$, so $- frac{2}{n + 1} leq - frac{2}{n + 2}$. For the second-to-last step, we can see that $frac{1}{n + 2} = frac{n + 1}{(n + 1)(n + 2)} = (n + 1) frac{1}{(n + 1)(n + 2)} geq frac{1}{(n + 1)(n + 2)}$.
$endgroup$
– AJY
1 hour ago
1
1
$begingroup$
So is this a step you saw you could implement to get the final equal to $ n + 1 - frac{1}{n + 2} $ ? Or is there something that would push you towards doing this?
$endgroup$
– Brownie
1 hour ago
$begingroup$
So is this a step you saw you could implement to get the final equal to $ n + 1 - frac{1}{n + 2} $ ? Or is there something that would push you towards doing this?
$endgroup$
– Brownie
1 hour ago
2
2
$begingroup$
@Brownie The short answer is that these kinds of tricks come easier with practice. We wanted to get to a very particular estimate, and just kinda made what estimates we could until it fell out just right. Sometimes (often) it just takes trial and error.
$endgroup$
– AJY
1 hour ago
$begingroup$
@Brownie The short answer is that these kinds of tricks come easier with practice. We wanted to get to a very particular estimate, and just kinda made what estimates we could until it fell out just right. Sometimes (often) it just takes trial and error.
$endgroup$
– AJY
1 hour ago
add a comment |
$begingroup$
Regarding the first inequality you're asking about, they are actually adding the term $frac{n+1}{n+2}$ to both sides, but on the left hand side it is added by increasing the upper limit in the sum by $1$, and to not change the inequality you have to add $frac{n+1}{n+2}$ to the right hand side.
The subsequent steps in the proof you posted are just rearrangements of fractions using algebra, nothing actually changes there until the last line. Then they just use the fact that $frac{1}{(n+1)(n+2)} leq frac{1}{n+2}$
$endgroup$
$begingroup$
Cool just last quick question, for the left hand side if instead of increasing the upper limit of the sum by 1, I added $frac{n+1}{n+2}$ to both sides, that would be the same?
$endgroup$
– Brownie
2 hours ago
$begingroup$
Yes, that would be the same.
$endgroup$
– Thomas Fjærvik
2 hours ago
add a comment |
$begingroup$
Regarding the first inequality you're asking about, they are actually adding the term $frac{n+1}{n+2}$ to both sides, but on the left hand side it is added by increasing the upper limit in the sum by $1$, and to not change the inequality you have to add $frac{n+1}{n+2}$ to the right hand side.
The subsequent steps in the proof you posted are just rearrangements of fractions using algebra, nothing actually changes there until the last line. Then they just use the fact that $frac{1}{(n+1)(n+2)} leq frac{1}{n+2}$
$endgroup$
$begingroup$
Cool just last quick question, for the left hand side if instead of increasing the upper limit of the sum by 1, I added $frac{n+1}{n+2}$ to both sides, that would be the same?
$endgroup$
– Brownie
2 hours ago
$begingroup$
Yes, that would be the same.
$endgroup$
– Thomas Fjærvik
2 hours ago
add a comment |
$begingroup$
Regarding the first inequality you're asking about, they are actually adding the term $frac{n+1}{n+2}$ to both sides, but on the left hand side it is added by increasing the upper limit in the sum by $1$, and to not change the inequality you have to add $frac{n+1}{n+2}$ to the right hand side.
The subsequent steps in the proof you posted are just rearrangements of fractions using algebra, nothing actually changes there until the last line. Then they just use the fact that $frac{1}{(n+1)(n+2)} leq frac{1}{n+2}$
$endgroup$
Regarding the first inequality you're asking about, they are actually adding the term $frac{n+1}{n+2}$ to both sides, but on the left hand side it is added by increasing the upper limit in the sum by $1$, and to not change the inequality you have to add $frac{n+1}{n+2}$ to the right hand side.
The subsequent steps in the proof you posted are just rearrangements of fractions using algebra, nothing actually changes there until the last line. Then they just use the fact that $frac{1}{(n+1)(n+2)} leq frac{1}{n+2}$
answered 2 hours ago
Thomas FjærvikThomas Fjærvik
2038
2038
$begingroup$
Cool just last quick question, for the left hand side if instead of increasing the upper limit of the sum by 1, I added $frac{n+1}{n+2}$ to both sides, that would be the same?
$endgroup$
– Brownie
2 hours ago
$begingroup$
Yes, that would be the same.
$endgroup$
– Thomas Fjærvik
2 hours ago
add a comment |
$begingroup$
Cool just last quick question, for the left hand side if instead of increasing the upper limit of the sum by 1, I added $frac{n+1}{n+2}$ to both sides, that would be the same?
$endgroup$
– Brownie
2 hours ago
$begingroup$
Yes, that would be the same.
$endgroup$
– Thomas Fjærvik
2 hours ago
$begingroup$
Cool just last quick question, for the left hand side if instead of increasing the upper limit of the sum by 1, I added $frac{n+1}{n+2}$ to both sides, that would be the same?
$endgroup$
– Brownie
2 hours ago
$begingroup$
Cool just last quick question, for the left hand side if instead of increasing the upper limit of the sum by 1, I added $frac{n+1}{n+2}$ to both sides, that would be the same?
$endgroup$
– Brownie
2 hours ago
$begingroup$
Yes, that would be the same.
$endgroup$
– Thomas Fjærvik
2 hours ago
$begingroup$
Yes, that would be the same.
$endgroup$
– Thomas Fjærvik
2 hours ago
add a comment |
$begingroup$
If $aleq b $, then $a+cleq b+c $ for any $cin Bbb R $. By assumption, we have $$sum_{k=1}^{n}frac k{k+1}leq n-frac 1{n+1}.$$ Now add $dfrac{n+1}{n+2}$ on both sides, i.e., $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$ Note that $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}=sum_{k=1}^{n+1}frac k{k+1}.$$ Hence we have $$sum_{k=1}^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$
$endgroup$
add a comment |
$begingroup$
If $aleq b $, then $a+cleq b+c $ for any $cin Bbb R $. By assumption, we have $$sum_{k=1}^{n}frac k{k+1}leq n-frac 1{n+1}.$$ Now add $dfrac{n+1}{n+2}$ on both sides, i.e., $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$ Note that $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}=sum_{k=1}^{n+1}frac k{k+1}.$$ Hence we have $$sum_{k=1}^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$
$endgroup$
add a comment |
$begingroup$
If $aleq b $, then $a+cleq b+c $ for any $cin Bbb R $. By assumption, we have $$sum_{k=1}^{n}frac k{k+1}leq n-frac 1{n+1}.$$ Now add $dfrac{n+1}{n+2}$ on both sides, i.e., $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$ Note that $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}=sum_{k=1}^{n+1}frac k{k+1}.$$ Hence we have $$sum_{k=1}^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$
$endgroup$
If $aleq b $, then $a+cleq b+c $ for any $cin Bbb R $. By assumption, we have $$sum_{k=1}^{n}frac k{k+1}leq n-frac 1{n+1}.$$ Now add $dfrac{n+1}{n+2}$ on both sides, i.e., $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$ Note that $$sum_{k=1}^{n}frac k{k+1}+frac{n+1}{n+2}=sum_{k=1}^{n+1}frac k{k+1}.$$ Hence we have $$sum_{k=1}^{n+1}frac k{k+1}leq n-frac 1{n+1}+frac{n+1}{n+2}.$$
edited 1 hour ago
answered 2 hours ago
Thomas ShelbyThomas Shelby
3,7192525
3,7192525
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.
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%2f3133089%2fplease-help-me-understand-the-following-solution%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