Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$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.

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks a lot, I got it now. Great help! –  user60334 Feb 23 '13 at 22:50
    
@user60334: You’re welcome, and thanks! –  Brian M. Scott Feb 23 '13 at 22:52

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.