Proving Induction Formula with Calculus - Maximilian

[dustwave]

Hello, I have this problem in my calculus class where I have to prove a formula with induction.

the problem is:

( 1 * 3 * 5 * ... * (2n - 1) ) / ( 1 * 2 * 3 * ... * n) =< 2^n

=< = equal or lesser than

P(1) is easy to solve, and so is P(k), but I start having problems with P(k+1) to prove the formula.. can someone give me a hand? =)

thanks!

/Maximilian

 

[HallsofIvy]

Yes, P(1) is "easy to solve": 1/1= 1< 2¹.
I'm not sure what you mean by saying P(k) is "easy to solve"- there's nothing to solve there!

You do, of course, assume that (1*2*...*(2k-1))/(1*2*...*k)<2^k

Now, for P(k+1), you have to look at (1*2*..*(2k-1)(2(k+1)-1)/(1*2*...*k*(k+1))
2(k+1)-1= 2k+1 of course, so this is
(1*2*...*(2k-1)*(2k+1)/(1*2*...*k*(k+1)= {(1*2*...*(2k-1))/(1*2*...*k)}{(2k+1)/(k+1)}< 2^k{(2k+1)/(k+1)}.

Looks to me like you need to prove that (2k+1)/(k+1)< 2 for all k! I would be inclined to write that as a "lemma" first and use induction to prove it.

 

[tongos]

(2n-1)!/{(2^(n-1)(n-1)!(n!)}=<2^n

{2^n(n!)}{2^(n-1)(n-1)!}>=(2n-1)!

(2n-1)!/(n!)(n-1)!=<2^(2n-1)

C(2n-1,n)=<2^(2n-1)
True?