2
$\begingroup$

For $n \geq 2$ prove that $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$

We need to use induction.

The Principle of Mathematical Induction, Theorem 4.2.1, states that $n_0 \in \mathbb{Z}$. For each integer $n \geq n_o$, let $P(n)$ be a statement about $n$. Suppose that the following two statements are true:

  1. $P(n_o)$
  2. $( \forall n \geq n_o)[P(n) \rightarrow P(n+1)]$

Then, for all integers $n \geq n_o$, that statement $P(n)$ is true.

Suppose, $(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$, the equation, is true for some natural number $k$.

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

The induction hypothesis $P(k) \rightarrow P(k+1)$ must hold for any natural number $k, P(k),$ from the basis and inductive step.

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

$\leftrightarrow$ $\frac{k+1}{2k}(\frac{(k+1)^2}{(k+1)^2}- \frac{1}{(k+1)^2})$

$\leftrightarrow$ $(\frac{(k+1)}{2k})( \frac{(k+1)^2-1}{(k+1)^2})$

$\leftrightarrow$ $( \frac{(k^2+2k+1-1}{(2k)(k+1)})$

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

$\leftrightarrow$ $( \frac{k+2}{(2)(k+1)})$

We need to demonstrate that

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

holds true for $n \geq 2$

The question is do I just substitute a number that is greater than two after I did the induction?

$\endgroup$
  • 2
    $\begingroup$ You have demonstrated that it is true. You just need to point it out (say, by writing "And thus, by induction, we have proved that..." instead of "We need to demonstrate that..."). Also, there is a small error in your notation(in the third line of your reasoning chain, the right-hand denominator should still be squared, but it's correct in subsequent lines) $\endgroup$ – Arthur Feb 4 '14 at 9:53
  • 1
    $\begingroup$ You are ready with this. The base step $P(2)$ is trivially true and in your question you prove that $P(k)$ implies $P(k+1)$. There is no need to switch from $n$ to $k$, though. $\endgroup$ – drhab Feb 4 '14 at 9:55
  • $\begingroup$ @Arthur where is the error? Is it in $(\frac{(k+1)}{2k})( \frac{(k+1)^2-1}{k+1})$ ? $\endgroup$ – usukidoll Feb 4 '14 at 10:03
  • 1
    $\begingroup$ Yes, the $k+1$ in the right denominator should be squared. $\endgroup$ – Arthur Feb 4 '14 at 10:07
  • $\begingroup$ Yes you're right. sorry fast fingers lol $\endgroup$ – usukidoll Feb 4 '14 at 10:09
2
$\begingroup$

The principle of Induction must be used in two steps, called basis and induction step.

For basis, you must check that the theorem or identity you want to prove is true for the "starting point" $n$; in your case, for $n = 2$.

So, you must check that :

$(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) = \frac{n+1}{2n}$

is true (and this is simple: put $n = 2$ inside the formula and see that LHS and RHS both give you $\frac{3}{4}$).

For the induction step, you must assume (i.e.suppose) that identity holds for $n$ (we call it induction hypotheses) and prove that (under this assumption) it holds also for $n+1$.

This is made by writing the LHS up to the $(n+1)$-th term as made of the sum or product or ... (it depends on your problem; it's harder to write in words than to calculate it) of the first $n$ terms and the $(n+1)$-th.

Then you exploit the induction hypotheses and substitute into the LHS the RHS of the induction hypo, add or sum to it the $(n+1)$-th term ... and see what happens.

So, in the end, your method is the correct one; provide that you correct the typo in the third line of the induction step, you wull get the correct result, as soon as (I prefer to work with $n$ in place of $k$) you realize that :

$\frac{n+2}{2(n+1)} = \frac{(n+1)+1}{2(n+1)}$

is exactly yhe RHS of your formula for the case $n+1$.

$\endgroup$
  • $\begingroup$ ah! It's the basis part that's driving me nuts. but ok if I substitute $n = 2$ on RHS, I would have $\frac{3}{4}$...what about on the left though? Unless I just subsitute $1-(\frac{1}{n^2})$ $\endgroup$ – usukidoll Feb 4 '14 at 9:59
  • $\begingroup$ Yes, you must substitute $2$ in place of $n$, using the "part of the formula" that stop at $n$; so it really reduce to $(1 - \frac{1}{n^2})$. $\endgroup$ – Mauro ALLEGRANZA Feb 4 '14 at 10:03
  • $\begingroup$ I got it to work! Thank you :D $\endgroup$ – usukidoll Feb 4 '14 at 10:06
4
$\begingroup$

Without Induction: $$ \begin{align} \prod_{k=2}^n\left(1-\frac1{k^2}\right) &=\prod_{k=2}^n\left[\left(1-\frac1k\right)\left(1+\frac1k\right)\right]\\ &=\prod_{k=2}^n\left(\frac{k-1}{k}\right)\prod_{k=2}^n\left(\frac{k+1}{k}\right)\\ &=\prod_{k=1}^{n-1}\left(\frac{k}{k+1}\right)\prod_{k=2}^n\left(\frac{k+1}{k}\right)\\ &=\frac12\color{#C00000}{\prod_{k=2}^{n-1}\left(\frac{k}{k+1}\right)}\cdot\frac{n+1}{n}\color{#C00000}{\prod_{k=2}^{n-1}\left(\frac{k+1}{k}\right)}\\ &=\frac{n+1}{2n} \end{align} $$


Comment on the Induction: The formula for the product of $n-1$ terms is is $\frac{n+1}{2n}$.

For $n=1$, the product of $0$ terms is $1$ and that is what the formula gives.

Term $n$ is $1-\frac1{(n+1)^2}$ so the product of $n$ terms is $$ \begin{align} \frac{n+1}{2n}\left(1-\frac1{(n+1)^2}\right) &=\frac{n+1}{2n}\cdot\frac{n(n+2)}{(n+1)^2}\\ &=\frac{n+2}{2(n+1)} \end{align} $$ which is the formula for $n$ terms.

$\endgroup$
  • $\begingroup$ The OP proved in his question that $P(k)$ implies $P(k+1)$. I think it must be something else that is bothering him (or her). $\endgroup$ – drhab Feb 4 '14 at 9:54
  • $\begingroup$ Besides the gender confusion... lol I'm just a girl with proof problems XD $\endgroup$ – usukidoll Feb 4 '14 at 9:55
  • $\begingroup$ And I want to know if I should just plug in any number that $n \geq 2$. Like let $n=3$ then.... like the left hand side and the right hand side should be equal... should I do that? $\endgroup$ – usukidoll Feb 4 '14 at 9:56
  • $\begingroup$ @usukidoll: I have added a comment on the induction. Let me know if you are still uncertain. $\endgroup$ – robjohn Feb 4 '14 at 10:08
1
$\begingroup$

My way doesn't use induction. It uses formulas $a^2-b^2=(a-b)(a+b)$ $$(1- \frac{1}{4})(1- \frac{1}{9})(1- \frac{1}{16})...(1- \frac{1}{n^2}) =\\=((1- \frac{1}{2})(1- \frac{1}{3})(1- \frac{1}{4})...(1- \frac{1}{n}))((1+ \frac{1}{2})(1+ \frac{1}{3})(1+\frac{1}{4})...(1+ \frac{1}{n})) = \\=(\frac12\cdot\frac23\cdot\frac34 \ldots \cdot\frac{n-1}{n}) (\frac32\cdot\frac43\cdot\frac54 \ldots \cdot\frac{n+1}{n})= \frac{1}{n}(\frac{1}{2}(n+1))=\frac{n+1}{2n}$$

$\endgroup$
  • 2
    $\begingroup$ That's nice, but it does not meet the need of the OP. $\endgroup$ – drhab Feb 4 '14 at 9:58
  • $\begingroup$ Sorry induction is required for this problem. $\endgroup$ – usukidoll Feb 4 '14 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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