I need a hint on a proof using mathematical induction

Question

I'm trying to prove that $k^k+1\ge2^k$ using mathematical induction but i'm missing something. How can i establish the binomial $(k+1)^{k+1}$? As a first step, i multiplied both sides by $2$ and $k$ but i can't get further than this without distorting things. Can someone give me a hint? Thanks in advance.

This needs clarification. For what sort of k are you trying to prove this? if, say, $k ≥ 2$ the inequality is obvious, no? — lulu, Jul 23 '15 at 15:36

Eclipse Sun · Answer 1 · 2015-07-23T15:58:32.823

1

Why bother use mathematical induction? For $k\ge2$, we have $k^k+1\ge2^k+1>2^k$.

Maybe prove $k^k\ge2^k$ ($k\ge2$) would be much easier. Since $$(k+1)^{k+1}>(k+1)k^k\ge(k+1)2^k>2^{k+1},$$ mathematical induction can easily be applied.

edited Jul 23 '15 at 15:58

answered Jul 23 '15 at 15:40

Eclipse Sun

9,338
21
44

you can't use ${ k }^{ k }+1\ge { 2 }^{ k }$ in proofe ${ k }^{ k }+1\ge { 2 }^{ k }$ – haqnatural Jul 23 '15 at 15:42
1

I only used $f(x)=x^k$ is increasing on $(0,+\infty)$ when $k>0$. – Eclipse Sun Jul 23 '15 at 15:48

haqnatural · Answer 2 · 2015-07-23T17:02:18.870

0

$k=1$ $$\\ { 1 }^{ 1 }+1\ge 2\\$$ $k=n$ $$\\ { n }^{ n }+1\ge { 2 }^{ n }\\$$ ${ \left( n+1 \right) }^{ n+1 }+1\ge \left( { n }^{ n+1 }+\left( n+1 \right) { n }^{ n }+...+1 \right) +1\ge { n }^{ n+1 }+1+{ n }^{ n }+1\ge { n }^{ n }+1+{ n }^{ n }+1=2\left( { n }^{ n }+1 \right) \ge { 2 }^{ n+1 }$

edited Jul 23 '15 at 17:02

answered Jul 23 '15 at 15:37

haqnatural

21,578

The calcs seem correct, but could you please write a couple of lines to link them together? Like this it's a bit sketchy. – Jul 23 '15 at 16:23
i tried it but couldn't – haqnatural Jul 23 '15 at 17:02
I may be wrong, but i dont think that's correct. Like, where are the binomial coëfficients (elements of Pascal's triangle) in your deduction? $(n^{n+1}+(n+1)n^n+...+1)$ is not a binomial expansion, or am i missing something? – Fabrizio Jul 23 '15 at 17:06
1

@Fabrizio see here https://en.wikipedia.org/wiki/Binomial_theorem – haqnatural Jul 23 '15 at 17:11
1

Ah yes now i see that it's a binomial expansion, but i don't see how $(n^{n+1}+(n+1)n^n+...+1)\ge n^{n+1}+1+n^n+1$. Do you use the $>$ relation ? I don't think that equality plays a role here...am i right? Also, where did you get that first $1$ in the second part of the inequality showed in this comment? – Fabrizio Jul 23 '15 at 17:27
1

i got it now thanks ! – Fabrizio Jul 23 '15 at 17:50

score 0 · Answer 3 · answered Jul 23 '15 at 15:40

First for $k=1$ it is true, i.e., $1^1 + 1 \geq 2^1$. Suppose that the statement is true for $k$ want to show it is true for $k+1$. We have $k^k +1 \geq 2^k$ want to show that $(k+1)^{k+1} +1 \geq 2^{k+1}$ is true.

$(k+1)^{k+1} = (k+1)^k \cdot (k+1) $

Lets use the fact $(k+1)^k \geq k^k +1 $ to see this you can return to the binomial expansion.

But we know that $k^k \geq 2^k +1 \Rightarrow k^k \geq 2^k-1$. Hence

$ k^k +1 \geq (2^k - 1) + 1\geq 2^k$.

$(k+1)^{k+1} \geq 2^k (k+1) \geq 2^k (2)$. The last $\geq$ is true since $k\geq 1$. Binomial Theorem https://en.wikipedia.org/wiki/Binomial_theorem

I need a hint on a proof using mathematical induction

3 Answers3