Proof by induction for rational function

[member 731016]

Homework Statement

Please see below

Relevant Equations

Please see below

For this problem,

My solution is

$P(x) = a_nx^n + a_{n - 1}x^{n - 1} + \cdots + a_1x + a_0$ where n is a member of the natural numbers

Base case (n = 1): $P(x) = a_0x^0 = a_0$

Thus $\lim_{x \to \infty} \frac{P(x)}{e^x} = \lim_{x \to \infty} \frac{a_0}{e^x} = a_0 \lim_{x \to \infty} \frac{1}{e^x} = a_0 \times 0 = 0$

Algebra of limits and result $\lim_{x \to \infty} \frac{1}{e^x} = 0$, base case $\lim_{x \to \infty} \frac{P(x)}{e^x} = 0$ holds for degree zero polynomial

For inductive hypothesis, $\lim_{x \to \infty} \frac{a_n x^n + a_{n - 1}x^{n - 1} + \cdots + a_1 x + a_0}{e^x} = 0$

To prove inductive hypothesis, consider $h = n + 1$

$\lim_{x \to \infty} \frac{a_hx^h + a_{h - 1}x^{h - 1} + \cdots + a_1x + a_0}{e^x} = \lim_{x \to \infty} \frac{a_{n + 1}x^{n + 1} + a_nx^n + \cdots + a_1x + a_0}{e^x} = \lim_{x \to \infty} \frac{a_{n + 1}x^{n + 1}}{e^x} + \lim_{x \to \infty} \frac{a_nx^n + \cdots + a_1x + a_0}{e^x} = a_{n + 1} \lim_{x \to \infty} \frac{x^{n+1}}{e^x} = a_{n + 1}\times 0 = 0$ QED.

Note I assume $\lim_{x \to \infty} \frac{x^{n + 1}}{e^x} = 0$

Is this proof please correct?

Thanks!

 

[fresh_42]

The idea looks ok, but I'm not sure you wrote the induction step correctly. We have ...

For inductive hypothesis, $\lim_{x \to \infty} \frac{a_n x^n + a_{n - 1}x^{n - 1} + \cdots + a_1 x + a_0}{e^x} = 0$

To prove inductive hypothesis, induction step , consider $h = n + 1.$

No need to introduce $h,$ you could go with $n+1$ instead.

$\lim_{x \to \infty} \frac{a_hx^h + a_{h - 1}x^{h - 1} + \cdots + a_1x + a_0}{e^x} = \lim_{x \to \infty} \frac{a_{n + 1}x^{n + 1} + a_nx^n + \cdots + a_1x + a_0}{e^x} = \lim_{x \to \infty} \frac{a_{n + 1}x^{n + 1}}{e^x} + \underbrace{\lim_{x \to \infty} \frac{a_nx^n + \cdots + a_1x + a_0}{e^x}}_{=0\, , \,I.H.}$

$= a_{n + 1} \lim_{x \to \infty} \frac{x^{n+1}}{e^x} + 0 = a_{n + 1}\times 0 + 0 = 0$ QED.

Note I assume $\lim_{x \to \infty} \frac{x^{n + 1}}{e^x} = 0$

This is what you have used for $n=1,$ too. Maybe you should prove by induction that $\lim_{x \to \infty}\dfrac{x^n}{e^x}=1$ before you write it down for general polynomials. Otherwise, your proof is circular since every polynomial can be put between $c_1x^n \leq P(x) \leq c_2x^n.$


Why do you know that $\displaystyle{\lim_{x \to \infty}}\dfrac{x^n}{e^x}=0$ for all $n\geq 0$? What's your definition of $e^x$?

 

[member 731016]

The idea looks ok, but I'm not sure you wrote the induction step correctly. We have ...

No need to introduce $h,$ you could go with $n+1$ instead.

This is what you have used for $n=1,$ too. Maybe you should prove by induction that $\lim_{x \to \infty}\dfrac{x^n}{e^x}=1$ before you write it down for general polynomials. Otherwise, your proof is circular since every polynomial can be put between $c_1x^n \leq P(x) \leq c_2x^n.$


Why do you know that $\displaystyle{\lim_{x \to \infty}}\dfrac{x^n}{e^x}=0$ for all $n\geq 0$? What's your definition of $e^x$?

Thank you for your reply @fresh_42!

Here is my proof by induction for $\displaystyle{\lim_{x \to \infty}}\dfrac{x^n}{e^x}=0$

By L'Hospitals rule we consider n = 1 as base case. Then $\lim_{x \to \infty} \frac{x}{e^x} = \lim_{x \to \infty} \frac{1}{e^x} = 0$ since $e^x$ is an exponential function.

To prove inductive step, consider $n + 1$ and we assume that $\lim_{x \to \infty} \frac{x^n}{e^x} = 0$ for inductive hypothesis.

$\lim_{x \to \infty} \frac{x^{n + 1}}{e^x} = \lim_{x \to \infty} \frac{xx^n}{e^x} = \lim_{x \to \infty} \frac{xx^n}{e^x} \lim_{x \to \infty} x = 0 \times \infty = 0$ By algebra of limits.

Is this please correct?

Also sorry I don't understand this part:
$c_1x^n \leq P(x) \leq c_2x^n.$

Thanks!

 

[fresh_42]

Thank you for your reply @fresh_42!

Here is my proof by induction for $\displaystyle{\lim_{x \to \infty}}\dfrac{x^n}{e^x}=0$

By L'Hospitals rule we consider n = 1 as base case. Then $\lim_{x \to \infty} \frac{x}{e^x} = \lim_{x \to \infty} \frac{1}{e^x} = 0$ since $e^x$ is an exponential function.

You need to start with $n=0$ because you used it. "because it is an exponential function" is no valid argument. If it was, than you would have been immediately done. You could as well say
$$
\lim_{x \to \infty} \dfrac{P(x)}{e^x}=0
$$
because $e^x$ is an exponential function.

Start with what you have: how do you define $x \longmapsto \dfrac{1}{e^x}$? And before you say as the inverse of $e^x$ I add: how do you define $x\longmapsto e^x$? The exponential growth has to be part of the proof. That exponential growth outnumbers polynomial growth is exactly what has to be proven.

Can you elaborate on how you applied (i.e. to which functions and derivatives) L'Hôpital?

To prove inductive step, consider $n + 1$ and we assume that $\lim_{x \to \infty} \frac{x^n}{e^x} = 0$ for inductive hypothesis.

$\lim_{x \to \infty} \frac{x^{n + 1}}{e^x} = \lim_{x \to \infty} \frac{xx^n}{e^x} = \lim_{x \to \infty} \frac{xx^n}{e^x} \lim_{x \to \infty} x = 0 \times \infty = 0$ By algebra of limits.

Is this please correct?

No. $0 \times \infty$ is not a number. It isn't even defined since
\begin{align*}
\lim_{x \to \infty} \left(\dfrac{1}{x}\cdot x^2\right)&=0 \times \infty=\infty \\
\lim_{x \to \infty} \left(\dfrac{1}{x}\cdot x\right)&=0 \times \infty=1 \\
\lim_{x \to \infty} \left(\dfrac{1}{x^2}\cdot x\right)&=0 \times \infty=0
\end{align*}

Also sorry I don't understand this part:
$c_1x^n \leq P(x) \leq c_2x^n.$

For large values of $x,$ those that are far away from any zero, we can always find constants $c_1,c_2\in \mathbb{R}$ such that our polynomial is bounded by polynomials of the form $c\cdot x^n,$ i.e. that $c_1x^n \leq P(x) \leq c_2x^n.$ We can do this probably for all values of $x$, but we only need large ones, $x \to \infty .$

With that we get
\begin{align*}
c_1x^n \leq &P(x) \leq c_2x^n\\
\dfrac{c_1x^n}{e^x}\leq &\dfrac{P(x)}{e^x}\leq \dfrac{c_2x^n}{e^x}\\
\lim_{x \to \infty}\dfrac{c_1x^n}{e^x}\leq &\lim_{x \to \infty}\dfrac{P(x)}{e^x}\leq \lim_{x \to \infty}\dfrac{c_2x^n}{e^x}\\
0\leq &\lim_{x \to \infty}\dfrac{P(x)}{e^x}\leq 0
\end{align*}

Always start with what you have, and that is $e^{-x}=\dfrac{1}{e^x}.$ How is it defined?

E.g. if you have $\displaystyle{e^{-x}=\sum_{k=0}^\infty \dfrac{(-x)^k}{k!}}$ then
$$
\dfrac{x^n}{e^x}=x^n e^{-x}=\sum_{k=0}^\infty \dfrac{x^n \cdot (-x)^k}{k!} =\ldots
$$
Maybe you have another definition. But cleaning up the room and listing what you have is always a good method to start with.

 

[fresh_42]

I think you can get away without a series definition if you have ...

Spoiler: L'Hôpital says (in our case):

$$
\lim_{x \to \infty} \dfrac{f'(x)}{g'(x)}=0 \Longrightarrow \lim_{x \to \infty} \dfrac{f(x)}{g(x)}=0
$$
With $f(x)=x^n$ and $g(x)=e^x$ we get
...
which is the induction step. (Don't forget to note how to get rid of the factor $n.$)

Remains to show that $\lim_{x \to \infty}\dfrac{1}{e^x}=0$ or $\lim_{x \to \infty} e^x=\infty$ which should be easier.

 

[WWGD]

You can use the Taylor series approximation of $e^x$ and, if $d$ is the degree of the polynomial P ; use $e^x=1+x+x^2+....+x^{d+1}+.... >x^{d+1}+...$ and consider $\frac {P(x)}{x^{d+1}}$.

 

[member 731016]

Thank you for your replies @fresh_42 and @WWGD!

For a non-proof by induction, I think we can use Taylors theorem:

I would insert a step about using taking the limit of the highlighted inequality. SOmething like $\lim_{x \to \infty} \frac{P(x)}{e^x} \leq \lim_{x \to \infty} \frac{(n + 1)! |P(x)|}{|x|^{n + 1}} = 0$

Apart from that does anybody else agree that this is an elegant and simple version of the proof?

Thanks!

 

[docnet]

Yes, a direct proof at this level is usually shorter and more concise than a proof by induction, and so I think it's better.