# Function proof

• Oct 19th 2009, 03:08 PM
CoraGB
Function proof
f(n) = [1-(1/2^2)]*[1-(1/3^2)]*...*[1-(1/n^2)] where f: N − {1}→Q

I need to use some small values of n to come up with a conjecture of F(n) and the prove it using induction.

So far I have:

Once I calculated some values I conjectured that f(n)=(n+1)/2n

So my basis is n=2, ([1-(1/2^2)] = 3/4 = (2+1)/2*2

Hypothesis is n=k, then [1-(1/2^2)]*[1-(1/3^2)]*...*[1-(1/k^2)] = (k+1)/2k

Induction Step: n=k+1,
[1-(1/2^2)]*[1-(1/3^2)]*...*[1-(1/k^2)]*[1-(1/(k+1)^2)] = [(k+1)+1]/2(k+1)

So the right side becomes k+2/(2k+2)

And the left side becomes k+1/2k*[1-(1/(k+1)2)]

I tried simplifying the left side but I am definitely not getting anything similar to the right side. Any advice?
• Oct 20th 2009, 10:08 AM
Hello CoraGB
Quote:

Originally Posted by CoraGB
f(n) = [1-(1/2^2)]*[1-(1/3^2)]*...*[1-(1/n^2)] where f: N − {1}→Q

I need to use some small values of n to come up with a conjecture of F(n) and the prove it using induction.

So far I have:

Once I calculated some values I conjectured that f(n)=(n+1)/2n

So my basis is n=2, ([1-(1/2^2)] = 3/4 = (2+1)/2*2

Hypothesis is n=k, then [1-(1/2^2)]*[1-(1/3^2)]*...*[1-(1/k^2)] = (k+1)/2k

Induction Step: n=k+1,
[1-(1/2^2)]*[1-(1/3^2)]*...*[1-(1/k^2)]*[1-(1/(k+1)^2)] = [(k+1)+1]/2(k+1)

So the right side becomes k+2/(2k+2)

And the left side becomes k+1/2k*[1-(1/(k+1)2)]

I tried simplifying the left side but I am definitely not getting anything similar to the right side. Any advice?

I agree with your conjecture. The induction proof goes like this:

$P(n)$ is the propositional function: $f(n) = \frac{n+1}{2n}$

So $P(k) \Rightarrow f(k) = \frac{k+1}{2k}$

$\Rightarrow f(k+1) = f(k)\Big(1-\frac{1}{(k+1)^2}\Big)$

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

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

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

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

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

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

$\Rightarrow P(k+1)$

You've already proved that $P(2)$ is true. Hence, by Induction, $P(n)$ is true for all $n \ge 2$.