Mathematical induction - - my challenge problem

[lookagain]

Let n belong to the set of integers.


Prove by mathematical induction:


\(\displaystyle 2n + 1 \choose {n} \)\(\displaystyle \ \le \ 2^{2n - 1} \ + \ n, \ \ \ \ n \ge \ 1\)

 

[eddybob123]

Let n belong to the set of integers.


Prove by mathematical induction:


\(\displaystyle 2n + 1 \choose {n} \)\(\displaystyle \ \le \ 2^{2n - 1} \ + \ n, \ \ \ \ n \ge \ 1\)

For n=1, we get

\(\displaystyle {3\choose 1}\leq 2^{2(1)-1}+1\)

which is certainly true. Now assume that the inequality holds for an arbitrary value k. We will show that the inequality holds for k+1.

\(\displaystyle {{2n+3}\choose{n+1}}\leq 2^{2n+1}+n+1\).

Using the identity

\(\displaystyle {n\choose k}={{n-1}\choose{k-1}}+{{n-1}\choose{k}}\)

we have

\(\displaystyle {{2n+1}\choose{n-1}}+2{{2n+1}\choose{n}}+{{2n+1}\choose{n+1}}\leq 2^{2n+1}+n+1\)

and

\(\displaystyle 2{{2n+1}\choose{n-1}}+2{{2n+1}\choose{n}}\leq 2^{2n+1}+n+1\)

From that point on I'm stuck. I guess you can't substitute the induction hypothesis into the LHS since it would be impossible to tell which side is greater.

 

[Nehushtan]

\(\displaystyle \displaystyle{2n+3\choose n+1}\)​

\(\displaystyle =\ \dfrac{(2n+3)!}{(n+1)!(n+2)!}\)

\(\displaystyle =\ \dfrac{(2n+3)(2n+2)}{(n+2)(n+1)}\cdot\dfrac{(2n+1)!}{n!(n+1)!}\)

\(\displaystyle \displaystyle=\ \frac{(2n+3)(2n+2)}{(n+2)(n+1)}\cdot{2n+1\choose n}\)

\(\displaystyle \leqslant\ \dfrac{(2n+3)(2n+2)}{(n+2)(n+1)}\left[2^{2n-1}+n\right]\)

\(\displaystyle =\ \dfrac{2n+3}{n+2}\left[2^{2n}+2n\right]\)

which can easily be proved to be less than or equal to \(\displaystyle 2^{2n+1}+n+1\).

 

[lookagain]

\(\displaystyle \displaystyle{2n+3\choose n+1}\)​

\(\displaystyle =\ \dfrac{(2n+3)!}{(n+1)!(n+2)!}\)

\(\displaystyle =\ \dfrac{(2n+3)(2n+2)}{(n+2)(n+1)}\cdot\dfrac{(2n+1)!}{n!(n+1)!}\)

\(\displaystyle \displaystyle=\ \frac{(2n+3)(2n+2)}{(n+2)(n+1)}\cdot{2n+1\choose n}\)

\(\displaystyle \leqslant\ \dfrac{(2n+3)(2n+2)}{(n+2)(n+1)}\left[2^{2n-1}+n\right]\)

\(\displaystyle =\ \dfrac{2n+3}{n+2}\left[2^{2n}+2n\right]\)

which can > > > easily be proved < < < * to be less than or equal to \(\displaystyle 2^{2n+1}+n+1\).

So long as we're clear that the "which can easily be proved" is an incomplete solution.

That is, the problem isn't solved.



* for you. \(\displaystyle \ \ \) As I'm wise enough not to speak for others, it's not an accident
that I don't type this phrase in posts.

 

[daon2]

I attempted this in the past but discovered, at least I think, that the standard way of inducting will not work (showing a single base case, and then showing the successor property). One would need to show at least a couple of base cases to get any useful inequality (e.g. check n=2). That is why the above inequality is "hard" to show for general positive integral n. In fact the proposed inequality in Nehushtan's post is not true for all positive real n larger than 1, but that inequality (he?) gave makes it rather straight-forward with a little tinkering.

But if n is at least 3, and this is "easy" ( actually, I should say "easier" than this problem, but yes, not a complete solution without proving this as well!):

\(\displaystyle 2^{2 n} +2n > n^3+2n^2\)

Then it is enough to show

\(\displaystyle [2^{2n+1}+n+1]-[2-\frac{1}{n+2}]*[2^{2n}+2n] = 1+\dfrac{2^{2 n}+2n}{n+2}-3n\)

is at least zero. Which is now easy due to the little lemma that needs to be proven: Assuming \(\displaystyle n\ge 3\)

\(\displaystyle 1+\dfrac{2^{2 n}+2n}{n+2}-3n > 1+\dfrac{n^3+2n^2}{n+2}-3n = n^2-3n+1 > n(n-3) \ge 0\)

For the lemma, we have \(\displaystyle n=3\) gives \(\displaystyle 64 > 54\) and if \(\displaystyle n=4\) we get \(\displaystyle 264 > 96\). Then assuming true for \(\displaystyle n\) at least 4,

\(\displaystyle 2^{2 n+2} +2n+2 = 4*[2^{2n}+2n] - 6n+2 > 4[n^3+2n^2]-6n+2\)

\(\displaystyle = 4n^3+8n^2-6n+2 = [n^3+3n^2+3n+1]+2n^2+4n+2 + [3n^2-10n]\)

\(\displaystyle = (n+1)^3+2(n+1)^2+3n[n-10/3] > (n+1)^3+2(n+1)^2+3n[4-10/3] > (n+1)^3+2(n+1)^2\)

 

[Nehushtan]

So long as we're clear that the "which can easily be proved" is an incomplete solution.

That is, the problem isn't solved.



* for you. \(\displaystyle \ \ \) As I'm wise enough not to speak for others, it's not an accident
that I don't type this phrase in posts.

Assume to the contrary that \(\displaystyle \dfrac{2n+3}{n+2}\left[2^{2n}+2n\right]\,>\,2^{2n+1}+n+1\). After simplifying, you would get

\(\displaystyle 3n^2+3n\ >\ 2^{2n}+2\)​

which can easily be proved to be false, therefore problem solved.

 

[lookagain]

Assume to the contrary that \(\displaystyle \dfrac{2n+3}{n+2}\left[2^{2n}+2n\right]\,>\,2^{2n+1}+n+1\). After simplifying, you would get

\(\displaystyle 3n^2+3n\ >\ 2^{2n}+2\)​

> > > which can easily be proved to be false, therefore problem solved. < < <

Your post is a non-solution and does not count.

Furthermore, you are a "repeat offender" of making a similar style candidate of a solution that doesn't count.

You are wasting your time typing "which can be easily proved, because 1) "easily" is subjective and its use

doesn't lend any more credence to your alleged solution, and 2) without the back-up of actually showing

this alleged "proof," it is heresay and does not count.

And, no, the "therefore" part of your comment does not follow at all.

I didn't even have to consider your top two lines of your post, because the last line of your

post with its eleven words, is sufficient in showing you not having dedication to carrying out

the completion of the work (the last parts of the proof). Walk the walk, don't just talk it.