# Proof by Induction Help Discrete Math?

So I've gotten to a point in this induction problem where I really don't know where to go.

I've gotten the equation down to this:

$$\frac{k(k+1)(2k+3)}{2(2k+1)(2k+3)} + \frac{2(k+1)^2}{2(2k+1)(2k+3)} = \frac{(k+1)(k+2)}{2(2k+3)}$$

$$\frac{1^2}{1(3)} + \frac{2^2}{2(3)} + ... + \frac{n^2}{(2n-1)(2n+1)} = \frac{n(n+1)}{2(2n+1)}$$

• But what are you trying to prove? :) What was the original problem? – Mankind Nov 27 '15 at 23:12

Combine like terms:

$$\frac{k(k+1)(2k+3)}{2(2k+1)(2k+3)} + \frac{2(k+1)^2}{2(2k+1)(2k+3)} = \frac{k(k+1)(2k+3) + 2(k+1)^2}{2(2k+1)(2k+3)}$$

Expand the numerator, then take out $2(k+1)$ from the top and bottom to get the correct result. Hope this helps!

Numerator becomes:$$k(k+1)(2k+3) + 2(k^2+2k+1) = 2 k^3+7k^2+7k+2$$

Now, factor out $2k+1$ by long division if necessary to get:

$$2 k^3+7k^2+7k+2 = (2k+1)(k+2)(k+1)$$

Now, the $2k+1$ terms cancel, leaving you with the same equation.

• When I expand the numerator though, I get 2k^3+7k^2+7k+2, how can I take out a 2(k+1)? – Zion Todd Nov 27 '15 at 23:25
• Do not expand it so early. Rearrange the terms first. – nicole Nov 27 '15 at 23:41
• If this is not possible, you can attack it by expanding all the terms, and then reducing it to what is required. – nicole Nov 27 '15 at 23:49
• Right, but I don't know how to reduce 2k^3+7k^2+7k+2 over 8k^2+16k+6. I would think that you couldn't cancel anything out from there anymore. – Zion Todd Nov 27 '15 at 23:51
• Oh wow long division is required here too. Jesus, I didn't even think about that. – Zion Todd Nov 27 '15 at 23:56

Ok, I am not sure how you got the first equation, but this is how you would prove this, assuming that you have already proven the base case (whatever that may be). Then, you assume this holds for $n = k$ (Induction Hypothesis). That is,

$$\frac{1^2}{1(3)} + \frac{2^2}{2(3)} + ... + \frac{k^2}{(2k-1)(2k+1)} = \frac{k(k+1)}{2(2k+1)}$$

Now, you need to show that this holds for $n = k+1$. In other words, that,

$$\frac{1^2}{1(3)} + \frac{2^2}{2(3)} + ... + \frac{(k+1)^2}{(2k+1)(2k+3)} = \frac{(k+1)(k+2)}{2(2k+3)}$$

However, we know that the $$\sum\limits_{i=1}^{k+1} \frac{i^2}{(2i-1)(2i+1)} = (\sum\limits_{i=1}^k \frac{i^2}{(2i-1)(2i+1)})+ \frac{(k+1)^2}{(2k+1)(2k+3)}$$(Meaning that the summation to $k+1$ is the summation to $k$ plus the $k+1$ term.) So, by substituting the value of the summation to $k$ (Induction Hypothesis), we get:

$$\sum\limits_{i=1}^{k+1} \frac{i^2}{(2i-1)(2i+1)} = \frac{k(k+1)}{2(2k+1)} + \frac{(k+1)^2}{(2k+1)(2k+3)}$$

Now, you show that

$$\frac{k(k+1)}{2(2k+1)} + \frac{(k+1)^2}{(2k+1)(2k+3)} = \frac{(k+1)(k+2)}{2(2k+3)}$$ to finish the proof.

• To make the left side equal the right, don't I have to find the least common denominator, which would be 2(2k+1)(2k+3)? – Zion Todd Nov 27 '15 at 23:39
• Yes, you do have to do that, – nicole Nov 27 '15 at 23:40
• Yeah, that's how I got the first equation in my question. Maybe I am doing the LCD wrong? I know both denominators have to be the same and for both of them to be 2(2k+1)(2k+3) I need to multiply the first fraction by (2k+3) top and bottom and the second fraction by 2 top and bottom. Which would then give the first equation I had in my question, no? – Zion Todd Nov 27 '15 at 23:42
• After doing the LCD I wouldn't know where to go next pretty much though. – Zion Todd Nov 27 '15 at 23:48