Prove by the principle of induction

[acrobaticelectron]

Homework Statement

I must find if this expression is true for any natural number

Relevant Equations

(n+n)=2^n(2n-1)

(expression given to be proven)
check for p(1)... 2=2

substitute (n+n) to

And here is the problem, I just can't find a way to continue solving this problem

 

[FactChecker]

Maybe I am missing something. Try plugging in a number like n=5.

 

[acrobaticelectron]

Maybe I am missing something. Try plugging in a number like n=5.

Maybe my understanding of the definition hasn't been correct, this is the exact definition of the exercise, thanks for your reply :)

 

[FactChecker]

Yes, that is very different. You have proven it is true for n=1. Now assume that it is true for a general n (including n=1) and see if you can use that to prove it is true for n+1.
So you want to prove that $((n+1)+1)\cdot((n+1)+2)\cdot\cdot\cdot((n+1)+(n+1)) = 2^{n+1}\cdot 1\cdot 3\cdot 5\cdot\cdot\cdot(2(n+1)-1)$
Try to reorganize that equation into one that relates to the n-equation that is assumed to be true.

 

[fresh_42]

Homework Statement:: I must find if this expression is true for any natural number
Relevant Equations:: (n+n)=2^n(2n-1)

(expression given to be proven)
check for p(1)... 2=2

substitute (n+n) to

And here is the problem, I just can't find a way to continue solving this problem

The formula in your revised version can be written as
$$
P(n)\, : \,\dfrac{(2n)!}{n!}=2^n\cdot \prod_{k=1}^{2n-1}(2k-1)
$$
You are correct with your induction base: $\dfrac{(2\cdot 1)!}{1!}=2=2^1 \cdot \prod_{k=1}^1(2k-1).$

Next, you may assume that $P(n)$ is true (the induction hypothesis). You can also assume that $P(m)$ is true for all $m\leq n$ but I don't think this is necessary.

Finally (the induction step), we must somehow prove $P(n+1).$ The advantage of a proof by induction is, that we can use $P(n)$ as a proven statement. However, $P(n+1)$ is what we must show.

That is
$$
P(n+1)\, : \,\dfrac{(2n+2)!}{(n+1)!}=(n+2)(n+3)\ldots (2n+2)\stackrel{!}{=}2^{n+1}\cdot 1\cdot 3 \ldots (2n+1)=2^{n+1}\cdot \prod_{k=1}^{2n+1}(2k-1)
$$

You must prove $(!)$. The way to do it, is to bring it into a form where you can apply $P(n).$

Hint: Start on the right and write the product as $c(n)\cdot 2^n\cdot \prod_{k=1}^{2n-1}(2k-1)$ with some integer $c(n)$ and apply the induction hypothesis to it. Then bring it into the requested form on the left.

 

[acrobaticelectron]

Yes, that is very different. You have proven it is true for n=1. Now assume that it is true for a general n (including n=1) and see if you can use that to prove it is true for n+1.
So you want to prove that $((n+1)+1)\cdot((n+1)+2)\cdot\cdot\cdot((n+1)+(n+1)) = 2^{n+1}\cdot 1\cdot 3\cdot 5\cdot\cdot\cdot(2(n+1)-1)$
Try to reorganize that equation into one that relates to the n-equation that is assumed to be true.

Thanks for your answer! I apreciate it , however my problem comes when I have to relate the equations, I am just not able to get the "right side" of the equation

 

[acrobaticelectron]

The formula in your revised version can be written as
$$
P(n)\, : \,\dfrac{(2n)!}{n!}=2^n\cdot \prod_{k=1}^{2n-1}(2k-1)
$$
You are correct with your induction base: $\dfrac{(2\cdot 1)!}{1!}=2=2^1 \cdot \prod_{k=1}^1(2k-1).$

Next, you may assume that $P(n)$ is true (the induction hypothesis). You can also assume that $P(m)$ is true for all $m\leq n$ but I don't think this is necessary.

Finally (the induction step), we must somehow prove $P(n+1).$ The advantage of a proof by induction is, that we can use $P(n)$ as a proven statement. However, $P(n+1)$ is what we must show.

That is
$$
P(n+1)\, : \,\dfrac{(2n+2)!}{(n+1)!}=(n+2)(n+3)\ldots (2n+2)\stackrel{!}{=}2^{n+1}\cdot 1\cdot 3 \ldots (2n+1)=2^{n+1}\cdot \prod_{k=1}^{2n+1}(2k-1)
$$

You must prove $(!)$. The way to do it, is to bring it into a form where you can apply $P(n).$

Hint: Start on the right and write the product as $c(n)\cdot 2^n\cdot \prod_{k=1}^{2n-1}(2k-1)$ with some integer $c(n)$ and apply the induction hypothesis to it. Then bring it into the requested form on the left.

Thanks for the detailed answer, it really gives me some insight on the exercise. Right now I am a first year engineering student so I'm not really able to understand how you get the intuition to just convert one expression to one another, i would like to know what rule did you follow so I can learn it myself, thanks a lot!

 

[FactChecker]

Thanks for your answer! I apreciate it , however my problem comes when I have to relate the equations, I am just not able to get the "right side" of the equation

As a homework problem, you will have to show us your work and we can make suggestions.
Try to rewrite each side into a form that uses the n-equation of that side.

 

[fresh_42]

Right now I am a first year engineering student so I'm not really able to understand how you get the intuition to just convert one expression to one another

Say $P(n)\, : \,LHS(n)=RHS(n).$ Then we must show $P(n+1)\, : \,LHS(n+1)=RHS(n+1).$

So we start with
\begin{align*}
RHS(n+1)&=2^{n+1}\cdot 1\cdot 3\cdot 5 \cdot\ldots\cdot (2(n+1)-1)\\
&=2\cdot \left(2^{n}\cdot 1\cdot 3\cdot 5 \cdot\ldots\cdot (2n-1)\right)\cdot (2n+1)\\
&=2\cdot (2n+1)\cdot RHS(n)\\
&\stackrel{induction}{=}2\cdot (2n+1)\cdot LHS(n)\\
&\ldots \text{ etc. } \ldots\\
&=LHS(n+1)
\end{align*}

 

[acrobaticelectron]

As a homework problem, you will have to show us your work and we can make suggestions.
Try to rewrite each side into a form that uses the n-equation of that side.

Hi, this is my work so far:

p(n)=(n+1)(n+2)(n+3)...(n+n)=2^n*1*3*5...(2n-1)

p(n+1)= (n+1+1)(n+2+1)(n+3+1)...(n+n)*(n+n+1)=2^(n+1)*1*3*5...(2n+1)

(n+1+1)(n+2+1)(n+3+1)...2^n*1*3*5...(2n-1)(n+n+1)=2^(n+1)*1*3*5...(2n+1)
this is were I get stuck, I'm just not able to solve this relationship

 

[fresh_42]

Hi, this is my work so far:

p(n)=(n+1)(n+2)(n+3)...(n+n)=2^n*1*3*5...(2n-1)

p(n+1)= (n+1+1)(n+2+1)(n+3+1)...(n+n)*(n+n+1)=2^(n+1)*1*3*5...(2n+1)

(n+1+1)(n+2+1)(n+3+1)...2^n*1*3*5...(2n-1)(n+n+1)=2^(n+1)*1*3*5...(2n+1)
this is were I get stuck, I'm just not able to solve this relationship

If you study post #9 and re-substitute my variables $LHS(n)=\dfrac{(2n)!}{n!}$ you will almost get the complete solution. It is important that you understand why these equations are there.

 

[FactChecker]

Hi, this is my work so far:

p(n)=(n+1)(n+2)(n+3)...(n+n)=2^n*1*3*5...(2n-1)

p(n+1)= (n+1+1)(n+2+1)(n+3+1)...(n+n)*(n+n+1)=2^(n+1)*1*3*5...(2n+1)

(n+1+1)(n+2+1)(n+3+1)...2^n*1*3*5...(2n-1)(n+n+1)=2^(n+1)*1*3*5...(2n+1)
this is were I get stuck, I'm just not able to solve this relationship

You don't want to "solve this relationship". You want to simplify both sides in "equal ways" to get two sides that are clearly equal.
Consider the right side. $2^{n+1}=2\cdot 2^n$ and $1\cdot 3\cdot 5\cdot \cdot\cdot\cdot (2n-1)\cdot (2n+1) = [1\cdot 3\cdot 5\cdot \cdot\cdot\cdot (2n-1)] \cdot (2n+1)$
So $RHS_{n+1} = 2\cdot RHS_n \cdot (2n+1) = 2\cdot (2n+1)\cdot RHS_n$.
Now do the same kind of thing with the left side. Then use the assumed fact that $LHS_n = RHS_n$ to divide out those factors from both sides. See where that goes.
Use that $A\cdot LHS_n = B \cdot RHS_n \iff A=B$

 

[PeroK]

Thanks for the detailed answer, it really gives me some insight on the exercise. Right now I am a first year engineering student so I'm not really able to understand how you get the intuition to just convert one expression to one another, i would like to know what rule did you follow so I can learn it myself, thanks a lot!

There's no intuition required, only a solid mathematical technique. It's just the discipline to follow the inductive steps without getting your logic all mixed up.

In this case the answer drops out from no more than technique. No special algebraic tricks are required.

 

[PeroK]

It may be worth describing the basic induction technique. Rather than RHS and LHS, I'll use $a(n)$ and $b(n)$.

In general we want to prove that$$\forall n \ge 1: a(n) = b(n)$$The idea of induction is that we can prove this by showing that$$a(1)=b(1)$$and$$\forall n \ge 1: a(n) = b(n) \Rightarrow a(n+1) = b(n+1)$$The basic technique to do this has several steps:

1) Show that $a(1) = b(1)$ by direct computation.

2) Assume that for some fixed value of $n$ we have $a(n) = b(n)$. We assume nothing about $n$ other than it is some number $\ge 1$.

3) Write down the expression for $a(n+1)$. This is done simply by plugging $n+1$ into the formula for $a$.

4) Express $a(n+1)$ in terms of $a(n)$. For example, it may be something of the form$$a(n+1) = ca(n) + d$$5) We know $a(n) = b(n)$ so we can express $a(n+1)$ in terms of $b(n)$. E.g. $$a(n+1) = cb(n) + d$$.6) Show that this expression equals $b(n+1)$. E.g. Show that$$cb(n) + d = b(n+1)$$Then we are done. Note that this last step may be simple or tricky. You may have to do a lot of work here.

That's the basic technique in cases like this and is perhaps a good introduction to thinking logically. In any case, steps 1-6 should make perfect sense before you tackle an inductive proof.

 

[SammyS]

Hi, this is my work so far:

p(n)=(n+1)(n+2)(n+3)...(n+n)=2^n*1*3*5...(2n-1)

p(n+1)= (n+1+1)(n+2+1)(n+3+1)...(n+n)*(n+n+1)=2^(n+1)*1*3*5...(2n+1)

(n+1+1)(n+2+1)(n+3+1)...2^n*1*3*5...(2n-1)(n+n+1)=2^(n+1)*1*3*5...(2n+1)
this is were I get stuck, I'm just not able to solve this relationship

You have a error in your expression for proposition, $P(n+1)$. It may be helpful to write it as follows.

$P(n+1)$ states that

$((n\!+\!1)\!+\!1)((n\!+\!1)+2)((n\!+\!1)\!+\!3),,,((n\!+\!1)\!+\!n)((n\!+\!1)\!+n\!+\!1) =2^{n+1}\!\cdot1\cdot3\cdot5\cdots(2(n\!+\!1)-\!1)$

Simplifying this (and listing some additional factors) gives for $P(n+1)$:

$(n\!+\!2)(n\!+\!3)(n\!+\!4),,,(2n)(2n\!+\!1)(2n\!+\!2) = 2^{n+1}\!\cdot1\cdot3\cdot5\cdots(2n\!-\!1)(2n\!+\!1)$

Compare that with your expression for $P(n)$ to see how to get from $P(n)$ to $P(n+1)$.