Proof by induction question.

S

Sonal7

Full Member
Joined
Oct 4, 2019
Messages
485
I am stuck on some algebra while doing this proof.
The questions states:
Prove by induction that for any positive integer n,

[MATH] \sum_{r=1}^{n}\ {\frac{4}{r(r+2) }= \frac{n(3n+5)} {(n+1)(n+2)} } [/MATH]
I assumed n =k.
[MATH] \sum_{r=1}^{k}\ {\frac{4}{k\left(k+2\right) }= \frac{k(3k+5)} {(k+1)(k+2)} } [/MATH]
Then did the induction:
[MATH] \sum_{r=1}^{(k+1)}\ {\frac{4}{k\left(k+2\right) }= \frac{k(3k+5)} {(k+1)(k+2)} }+\frac{4}{(k+1)(k+3)} [/MATH][MATH] =\frac {k(3k+5)(k+3)+4(k+2)}{(k+1)(k+2)(k+3)} [/MATH]but now i am lost as to how to get it looking like the original formula with k+1 instead of k
 
Sonal7 said:
I am stuck on some algebra while doing this proof.
The questions states:
Prove by induction that for any positive integer n,

[MATH] \sum_{r=1}^{n}\ {\frac{4}{r(r+2) }= \frac{n(3n+5)} {(n+1)(n+2)} } [/MATH]
I assumed n =k.
[MATH] \sum_{r=1}^{k}\ {\frac{4}{k\left(k+2\right) }= \frac{k(3k+5)} {(k+1)(k+2)} } [/MATH]
Then did the induction:
[MATH] \sum_{r=1}^{(k+1)}\ {\frac{4}{k\left(k+2\right) }= \frac{k(3k+5)} {(k+1)(k+2)} }+\frac{4}{(k+1)(k+3)} [/MATH][MATH] =\frac {k(3k+5)(k+3)+4(k+2)}{(k+1)(k+2)(k+3)} [/MATH]but now i am lost as to how to get it looking like the original formula with k+1 instead of k
Click to expand...
You skipped a step. Please look up how proof by induction works.
 
Let's go back to the induction hypothesis:

[MATH]\sum_{r=1}^{n}\frac{4}{r(r+2) }= \frac{n(3n+5)} {(n+1)(n+2)}[/MATH]
If you wish to change \(n\) to \(k\), which isn't necessary but does no harm, then you want:

[MATH]\sum_{r=1}^{k}\frac{4}{r(r+2) }= \frac{k(3k+5)} {(k+1)(k+2)}[/MATH]
Now, as your induction step, you are going to want to add the same thing to both sides of the equation:

[MATH]\sum_{r=1}^{k}{\frac{4}{r(r+2) }+\frac{4}{(k+1)((k+1)+2)}= \frac{k(3k+5)} {(k+1)(k+2)} }+\frac{4}{(k+1)((k+1)+2)}[/MATH]
And of course the LHS becomes:

[MATH]\sum_{r=1}^{k+1}\frac{4}{r(r+2) }= \frac{k(3k+5)} {(k+1)(k+2)}+\frac{4}{(k+1)((k+1)+2)}[/MATH]
Now you need to show that the RHS is:

[MATH]\frac{(k+1)(3(k+1)+5)} {((k+1)+1)((k+1)+2)}[/MATH]
 
MarkFL said:
Let's go back to the induction hypothesis:

[MATH]\sum_{r=1}^{n}\frac{4}{r(r+2) }= \frac{n(3n+5)} {(n+1)(n+2)}[/MATH]
If you wish to change \(n\) to \(k\), which isn't necessary but does no harm, then you want:

[MATH]\sum_{r=1}^{k}\frac{4}{r(r+2) }= \frac{k(3k+5)} {(k+1)(k+2)}[/MATH]
Now, as your induction step, you are going to want to add the same thing to both sides of the equation:

[MATH]\sum_{r=1}^{k}{\frac{4}{r(r+2) }+\frac{4}{(k+1)((k+1)+2)}= \frac{k(3k+5)} {(k+1)(k+2)} }+\frac{4}{(k+1)((k+1)+2)}[/MATH]
And of course the LHS becomes:

[MATH]\sum_{r=1}^{k+1}\frac{4}{r(r+2) }= \frac{k(3k+5)} {(k+1)(k+2)}+\frac{4}{(k+1)((k+1)+2)}[/MATH]
Now you need to show that the RHS is:

[MATH]\frac{(k+1)(3(k+1)+5)} {((k+1)+1)((k+1)+2)}[/MATH]
Click to expand...
I am trying to get to it, but I cant see how. I cant see that we need 8 in the numerator and we need to eliminate (k+1) from the denominator.
 
Sonal7 said:
I am trying to get to it, but I cant see how. I cant see that we need 8 in the numerator and we need to eliminate (k+1) from the denominator.
Click to expand...

Let's rewrite the RHS as:

[MATH]\frac{k(3k+5)}{(k+1)(k+2)}+\frac{4}{(k+1)(k+3)}[/MATH]
Now combine terms:

[MATH]\frac{k(3k+5)(k+3)+4(k+2)}{(k+1)(k+2)(k+3)}[/MATH]
If we expand the numerator, we get:

[MATH]3k^3+14k^2+19k+8[/MATH]
We can see we need \(k+1\) to be a factor...is \(k=-1\) a zero of the above expression?
 
I was on the right track it seems, it looked like a mess to me but I didnt think of putting in -1 to check that it was a factor!
 
Yes, I find it is, and so what you you get when doing the division?
 
[MATH] =\frac{(k+1)(k+1)(3k+8)}{(k+1)(k+2)(k+3)} [/MATH]I was smart this time. I substituted x=-1 again as I thought it was a repeated root.
 
Sonal7 said:
[MATH] =\frac{(k+1)(k+1)(3k+8)}{(k+1)(k+2)(k+3)} [/MATH]I was smart this time. I substituted x=-1 again as I thought it was a repeated root.
Click to expand...

Nicely done...looks like you're in the home stretch now! :)
 
I must admit that I like to separate n and k as well. And you can solve just by factoring since you know where you want to end up.

[MATH]\text {PROVE: } n \in \mathbb Z \text { and } n \ge 1 \implies \sum_{r=1}^n \dfrac{4}{r(r + 2)} = \dfrac{n(3n + 5)}{(n + 1)(n + 2)}.[/MATH]
[MATH]n = 1 \implies \sum_{r=1}^n \dfrac{4}{r(r + 2)} = \dfrac{4}{1(1 + 2)} = \dfrac{4}{3} = \dfrac{8}{6} =[/MATH]
[MATH]\dfrac{1 * 8}{2 * 3} = \dfrac{1 * (5 * 1 + 3)}{(1 + 1)(1 + 3)} = \dfrac{n(3n + 5)}{(n + 1)(n + 2)}.[/MATH]
Thus we have justified this statement

[MATH]\exists \text { non-empty set } \mathbb K \text { such that }[/MATH]
[MATH]k \in \mathbb K \implies s \in \mathbb Z,\ k \ge 1, \text { and } \sum_{r=1}^k \dfrac{4}{r(r + 2)} = \dfrac{k(3k + 5)}{(k + 1)(k + 2)}.[/MATH]
[MATH]\text {Let } k \text { be an ARBITRARY member of } \mathbb S.[/MATH]
[MATH]\sum_{r=1}^{k+1} \dfrac{4}{(r(r + 2)} = \left ( \sum_{r=1}^k \dfrac{4}{(r(r + 2)} \right ) + \dfrac{4}{(k + 1)\{(k + 1) + 2\}} =[/MATH]
[MATH]\dfrac{k(3k + 5)}{(k + 1)(k + 2)} + \dfrac{4}{(k + 1)(k + 3)} = \dfrac{(3k^2 + 5k)(k + 3)}{(k + 1)(k + 2)(k + 3)} + \dfrac{4(k + 2)}{(k + 1)(k + 2)(k + 3)} =[/MATH]
[MATH]\dfrac{3k^3 + 14k^2 + 19k + 8}{(k + 1)(k + 2)(k + 3)} = \dfrac{(k^2 + 2k + 1)(3k + 8)}{(k + 1)(k + 2)(k + 3)} =\dfrac{(k + 1)^2(3k + 8)}{(k + 1)(k + 2)(k + 3)}[/MATH]
[MATH]\dfrac{(k + 1)(3k + 8)}{(k + 2)(k + 3)} = \dfrac{(k + 1)\{3(k + 1) + 5\}}{\{(k + 1) + 1\})\{(k + 1) + 2\}.}[/MATH]
 
Last edited:
Thanks that's a great tip. I just get worried I won't see the form required but it's easier to see once the factorisation has been done.
 
Sonal7 said:
Thanks that's a great tip. I just get worried I won't see the form required but it's easier to see once the factorisation has been done.
Click to expand...
Of course you will see the form required. It will ALWAYS be like the original formula with k+1 instead of k, just as you said.
 
Sonal7 said:
I just get worried I won't see the form required but it's easier to see once the factorisation has been done.
Click to expand...

One thing I do before starting the actual work on the induction step is to simplify the expected result. That is, in this example, I would write out

[MATH]\frac{(k+1)(3(k+1)+5)} {((k+1)+1)((k+1)+2)}[/MATH],​

which the k+1 case should turn out equalling, and expand it to

[MATH]\frac{3k^2 + 11k + 8} {(k+2)(k+3)}[/MATH].​

If I can factor that, I might, but that isn't essential.

Then when I got

[MATH]\frac {k(3k+5)(k+3)+4(k+2)}{(k+1)(k+2)(k+3)}[/MATH]​

for the new sum, I would expand that, but also I would observe that its denominator has an extra factor, [MATH](k+1)[/MATH], beyond what is needed; so I might in anticipation multiply numerator and denominator of my "goal" by [MATH](k+1)[/MATH], to make it look like what I will get on the LHS. If it matches, I'm done.

The idea is that I know what I want to get, so I can put that goal in the same form I expect to obtain, so it will be easy to recognize. I don't have to arrive at the goal blindly, just happening to put it in the right form; I can have the goal set up to be easily seen.
 
You must log in or register to reply here.
Top