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
add comment

3 Answers

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
add comment

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
add comment

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
add comment

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.