Proving $\prod((k^2-1)/k^2)=(n+1)/(2n)$ by induction

Question

$$P_n = \prod^n_{k=2} \left(\frac{k^2 - 1}{k^2}\right)$$ Someone already helped me see that $$P_n = \frac{1}{2}.\frac{n + 1}{n} $$ Now I have to prove, by induction, that the formula for $P_n$ is correct. The basis step: $n = 2$ is true, $$P_2 = \frac{3}{4} = \frac{1}{2}.\frac{2+1}{2} $$ Inductive step: Assuming $P_k = \frac12.\frac{k+1}k$ is true for $k \ge2$, I need to prove $$P_{k+1} = \frac12.\frac{k+2}{k+1}$$ So I am stuck here, I have been playin around with $P_k$ and $P_{k+1}$ but I can't figure out how to connect the hypothesis with what I am trying to prove.

Answer 1

Suppose that $P_n=\dfrac{n+1}{2n}$; for your induction step you want to prove that $$P_{n+1}=\frac{(n+1)+1}{2(n+1)}=\frac{n+2}{2(n+1)}\;.$$

By definition $$P_{n+1}=\prod_{k=2}^{n+1}\frac{k^2-1}{k^2}=\left(\prod_{k=2}^n\frac{k^2-1}{k^2}\right)\left(\frac{(n+1)^2-1}{(n+1)^2}\right)\;.\tag{1}$$

Your induction hypothesis tells you that $$\prod_{k=2}^n\frac{k^2-1}{k^2}=\frac{n+1}{2n}\;,$$ so

$$P_{n+1}=\frac{n+1}{2n}\cdot\frac{(n+1)^2-1}{(n+1)^2}\;.$$

Can you finish the induction step from here?

The technique that I used at $(1)$ of splitting the product into an old part and a new part in such a way that the induction hypothesis let me simplify the old part is a very common one in these problems. More generally, in trying to carry out the induction step you want to look for a way to use the induction hypothesis. When you’re trying to prove a closed form for a sum or product, splitting off the old part of the sum or product and using the induction hypothesis to simplify it is the first thing to try.

Answer 2

We do the same thing as in the solution of Brian M. Scott, but slightly backwards, We are interested in the question $$\frac{n+2}{2(n+1)}\overset{?}{=}\frac{n+1}{2n}\frac{(n+1)^2-1}{(n+1)^2}.$$ The difference-of-squares factorization $(n+1)^2-1=(n)(n+2)$ settles things.

Answer 3

It's trivial by telescopy. One easily sees how to inductively prove this telescoping product formula

$$\rm f(0)\ \prod_{k\:=\:0}^{m-1}\, \frac{f(k\!+\!1)}{f(k)}\ = \ \ \color{red}{\rlap{--}f(0)}\frac{\color{green}{\rlap{--}f(1)}}{\color{red}{\rlap{--}f(0)}}\frac{\color{royalblue}{\rlap{--}f(2)}}{\color{green}{\rlap{--}f(1)}}\frac{\phantom{\rlap{--}f(3)}}{\color{royalblue}{\rlap{--}f(2)}} \, \cdots \frac{\color{brown}{\rlap{---}f(m\!-\!1)}}{\phantom{\rlap{--}f(m\!-\!2)}}\frac{f(m)}{\color{brown}{\rlap{----}f(m-1)}}\ =\ \ f(m) $$

Applying this twice, starting at $\rm\ k =2\ $ vs. $\rm\ k=0,\ $ gives

$$\begin{eqnarray}\rm \prod_{k=2}^n\, \dfrac{f(k\!-\!1)}{f(k)} &\, =\, &\rm \dfrac{f(1)}{f(n)} \\ \\ \rm\prod_{k=2}^n \dfrac{f(k\!+\!1)}{f(k)} &\, =\, &\rm \dfrac{f(n\!+\!1)}{f(2)} \\ \\ \rm \Rightarrow\ \ \prod_{k=2}^n \dfrac{f(k\!-\!1)\,f(k\!+\!1)}{f(k)\ \ \ \ \ f(k)} &\, =\, &\rm \dfrac{f(1)\, f(n\!+\!1) }{f(2)\ \ f(n)\ \ \ }\end{eqnarray}$$

Yours is the special case $\rm\ f(k) = k\ $ of the above.