Induction Proof

Clifford

Junior Member
Joined
Nov 15, 2006
Messages
81
Prove by induction that \(\displaystyle \L 1\, + \,\frac{1}{2^2 }\, + \,\frac{1}{3^2}\, +\, ...\, + \,\frac{1}{n^2 }\, \,2\, - \,\frac{1}{n}\) for all positive integers of n.

Solving for P(1), we get the LS = RS, which makes it true, we then assume it works for P(k). We then must prove it works for P(K+1)

Trying to work it out, I came up with:

\(\displaystyle \L 1 + \;\frac{1}{2^2 }\; + \;\frac{1}{3^2 }\; + \;...\; + \;\frac{1}{n^2}\; + \;\frac{1}{\left( {k + 1} \right)^2 } \; \;2\; - \;\frac{1}
{k}\; + \;\frac{1}{\left( {k + 1} \right)^2 }\)
\(\displaystyle \L 1 + \;\frac{1}
{{2^2 }}\; + \;\frac{1}
{{3^2 }}\; + \;...\; + \;\frac{1}
{{n^2 }}\; + \;\frac{1}
{{\left( {k + 1} \right)^2 }}\; 2\; - \;\frac{{\left( {k + 1} \right)^2 }}
{{k\left( {k + 1} \right)^2 }}\; + \;\frac{k}
{{k\left( {k + 1} \right)^2 }}\)

\(\displaystyle \L
1 + \;\frac{1}
{{2^2 }}\; + \;\frac{1}
{{3^2 }}\; + \;...\; + \;\frac{1}
{{n^2 }}\; + \;\frac{1}
{{\left( {k + 1} \right)^2 }}\; \;2\; - \;\frac{{\left( {k + 1} \right)^2 + k}}
{{k\left( {k + 1} \right)^2 }}\)

\(\displaystyle \L
1 + \;\frac{1}
{{2^2 }}\; + \;\frac{1}
{{3^2 }}\; + \;...\; + \;\frac{1}
{{n^2 }}\; + \;\frac{1}
{{\left( {k + 1} \right)^2 }}\; \;2\; - \;\frac{{\left( {k^2 + 2k + 1} \right) + k}}
{{k\left( {k^2 + 2k + 1} \right)}}\)

\(\displaystyle \L
1 + \;\frac{1}
{{2^2 }}\; + \;\frac{1}
{{3^2 }}\; + \;...\; + \;\frac{1}
{{n^2 }}\; + \;\frac{1}
{{\left( {k + 1} \right)^2 }}\; \;2\; - \;\frac{{\left( {k^2 + k + 1} \right)}}
{{k\left( {k^2 + 2k + 1} \right)}}\)

I think the answer I am trying to derive is: \(\displaystyle \[
2 - \;\frac{1}
{{k + 1}}
\]\)

I am stuck here. I was wondering if somebody could let me know if what I am doing is right, if I made an error somewhere, and could help me out so I can complete the question.

Thanks.
 

stapel

Super Moderator
Staff member
Joined
Feb 4, 2004
Messages
15,943
Is there maybe supposed to be an "equals" or an inequality in there somewhere...? :shock:

Eliz.
 

Clifford

Junior Member
Joined
Nov 15, 2006
Messages
81
Yeah, sorry but I am not very good with tex

\(\displaystyle \L \left[1\, +\, \frac{1}{2^2}\, +\, \frac{1}{3^2}\, +\, \ldots\, +\, \frac{1}{k^2}\, +\, \frac{1}{\left( {k\, +\, 1} \right)^2 }\right]\, \leq \,\left[2\, -\,\frac{1}{k}\, + \,\frac{1}{\left( {k\, +\, 1} \right)^2 }\right]\)

\(\displaystyle \L \left[1\, + \,\frac{1}{2^2}\, + \,\frac{1}{3^2}\,+\, \ldots\, + \, \frac{1}{k^2}\, + \, \frac{1}{\left(k\, + \,1\right)}\right]\, \leq \,\left[2\, - \frac{\left(k\,+\,1\right)^2}{k\left(k\,+\,1\right)^2}\,+\,\frac{k}{k\left(k\,+\,1\right)^2}\right]\)

\(\displaystyle \L \left[1\, + \,\frac{1}{2^2}\, + \,\frac{1}{3^2}\,+\, \ldots\, + \, \frac{1}{k^2}\, + \, \frac{1}{\left(k\, + \,1\right)}\right]\, \leq \,\left[2\, -\, \frac{\left(k\, +\, 1\right)^2\, +\, k}{k\left(k\, +\, 1\right)^2}\right]\)

\(\displaystyle \L \left[1\, + \,\frac{1}{2^2}\, + \,\frac{1}{3^2}\,+\, \ldots\, + \, \frac{1}{k^2}\, + \, \frac{1}{\left(k\, + \,1\right)}\right]\, \leq \, \left[2\, -\, \frac{k^2\, +\, k\, +\, 1}{k\left(k^2\, +\, 2k\, +\, 1\right)}\right]\)

______________________________________
Edited by stapel -- Reason for edit: Correcting formatting.
 

stapel

Super Moderator
Staff member
Joined
Feb 4, 2004
Messages
15,943
Okay, I think you mean that you need to show the following:

. . . . .1/1<sup>2</sup> + 1/2<sup>2</sup> + 1/3<sup>2</sup> + ... + 1/n<sup>2</sup> < 2 - 1/n

If so, then the assumption step, for n = k, is:

. . . . .1/1<sup>2</sup> + 1/2<sup>2</sup> + 1/3<sup>2</sup> + ... + 1/k<sup>2</sup> < 2 - 1/k

Then let n = k + 1, and:

. . . . .1/1<sup>2</sup> + 1/2<sup>2</sup> + 1/3<sup>2</sup> + ... + 1/k<sup>2</sup> + 1/(k + 1)<sup>2</sup>

. . . . .= (1/1<sup>2</sup> + 1/2<sup>2</sup> + 1/3<sup>2</sup> + ... + 1/k<sup>2</sup>) + 1/(k + 1)<sup>2</sup>

. . . . .< (2 - 1/k) + 1/(k + 1)<sup>2</sup>

. . . . .= 2 - (k + 1)<sup>2</sup>/(k(k + 1)<sup>2</sup>) + k/(k(k + 1)<sup>2</sup>

. . . . .= 2 - [(k + 1)<sup>2</sup> - k] / [k (k + 1)<sup>2</sup>]

Simplify inside the brackets. Then note that, if you subtract something smaller, you'll get something bigger. :idea:

Is there any strategic deletion from "k<sup>2</sup> + k + 1" that you can do, which will make the numerator smaller (so, after subtracting from 2, you get something bigger), and which will allow you to cancel off the k and one of the k + 1 factors...? :wink:

Eliz.
 
Top