Welcome to our community

Be a part of something great, join today!

Induction Help

crypt50

New member
Jun 29, 2013
21
Show using induction that
(1 + 1 / n + 1).(1 + 1 / n + 2). ... . (1 + 1 / n + n) = 2 - 1 / n + 1, n >= 1.

I've tried everything with this question but the right hand side is not the same as the left hand side after substituting k+1 in the place of n, please help.
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
I have moved this topic, as it is a better fit with discrete mathematics than number theory.

I am assuming (given the lack of bracketing symbols) that you are given to prove:

\(\displaystyle \prod_{j=1}^n\left(1+\frac{1}{n+j} \right)=2-\frac{1}{n+1}\) where \(\displaystyle n\in\mathbb{N}\).

The first thing we wish to do is demonstrate the base case \(\displaystyle P_1\) is true:

\(\displaystyle \prod_{j=1}^1\left(1+\frac{1}{1+j} \right)=2-\frac{1}{1+1}\)

\(\displaystyle 1+\frac{1}{1+1}=2-\frac{1}{1+1}\)

\(\displaystyle \frac{3}{2}=\frac{3}{2}\)

Thus, the base case is true.

Next, state the induction hypothesis $P_k$:

\(\displaystyle \prod_{j=1}^k\left(1+\frac{1}{k+j} \right)=2-\frac{1}{k+1}\)

Let's combine the two terms within the product:

\(\displaystyle \prod_{j=1}^k\left(\frac{k+j+1}{k+j} \right)=2-\frac{1}{k+1}\)

Let's pull out the first factor on the left.

\(\displaystyle \frac{k+2}{k+1}\prod_{j=2}^k\left(\frac{k+j+1}{k+j} \right)=2-\frac{1}{k+1}\)

This will allow us to re-index the product and replace $k$ with $k+1$:

\(\displaystyle \frac{k+2}{k+1}\prod_{j=1}^{k-1}\left(\frac{(k+1)+j+1}{(k+1)+j} \right)=\frac{2k+1}{k+1}\)

Next, multiply through by \(\displaystyle \frac{k+1}{k+2}\):

\(\displaystyle \prod_{j=1}^{k-1}\left(\frac{(k+1)+j+1}{(k+1)+j} \right)=\frac{2k+1}{(k+1)+1}\)

Now, try as your induction step, multiplying by:

\(\displaystyle \prod_{j=k}^{k+1}\left(\frac{(k+1)+j+1}{(k+1)+j} \right)=\frac{2(k+1)+1}{2k+1}\)

What do you find?

Incidentally, there is an easier way to demonstrate the identity is true (if we hadn't been directed to use induction)...let's write the identity as:

\(\displaystyle \prod_{j=1}^n\left(\frac{n+j+1}{n+j} \right)=2-\frac{1}{n+1}\)

Now, we may choose to express this as:

\(\displaystyle \frac{\prod\limits_{j=1}^n\left(n+j+1 \right)}{\prod\limits_{j=1}^n\left(n+j \right)}=2-\frac{1}{n+1}\)

\(\displaystyle \frac{\prod\limits_{j=2}^{n+1}\left(n+j \right)}{(n+1)\prod\limits_{j=2}^{n}\left(n+j \right)}=2-\frac{1}{n+1}\)

\(\displaystyle \frac{(n+(n+1))\prod\limits_{j=2}^{n}\left(n+j \right)}{(n+1)\prod\limits_{j=2}^{n}\left(n+j \right)}=2-\frac{1}{n+1}\)

\(\displaystyle \frac{2n+1}{n+1}=2-\frac{1}{n+1}\)

\(\displaystyle \frac{2(n+1)-1}{n+1}=2-\frac{1}{n+1}\)

\(\displaystyle 2-\frac{1}{n+1}=2-\frac{1}{n+1}\)
 

crypt50

New member
Jun 29, 2013
21
The question did not include the product sign was why I couldn't figure it out, thank u so much for your help.