0

I was basically given a Pascal Triangle formula and asked to provide an asymptotic upper bound.

I have done some work and ended with expression below

${n^k} \ge {n(n-1)^{(k-1)}}$

now I am trying to justify that LHS $\ge$ RHS is always true for all positive integer n and k

tried to use proof by induction but stuck with the second phase, can you even prove with inequality, I might be using the wrong prove, direct me with anything useful thanks

DSt_FTW
  • 41

1 Answers1

1

You don't need induction to prove this. For any positive integer $k$ and $n(>1)$,

$n^k=n.n^{k-1}$

So, the question just reduces to show that

$n^{k-1}\geqq (n-1)^{k-1}$

which is true since $\frac{n}{n-1}\geqq1$ for all $n>1$.

It holds trivially if $n=1$

Ankit Kumar
  • 1,874