# Induction Proof

#### Clifford

##### Junior Member
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
Is there maybe supposed to be an "equals" or an inequality in there somewhere...? :shock:

Eliz.

#### Clifford

##### Junior Member
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
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.