# Proof by induction for rational function

• member 731016
member 731016
Homework Statement
Relevant Equations
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##

Thanks!

The idea looks ok, but I'm not sure you wrote the induction step correctly. We have ...
ChiralSuperfields said:
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.
ChiralSuperfields said:
##\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##?

docnet and member 731016
fresh_42 said:
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##?

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.

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

Thanks!

ChiralSuperfields said:

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?

ChiralSuperfields said:
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.

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*}
ChiralSuperfields said:
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.

docnet and member 731016
I think you can get away without a series definition if you have ...
$$\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.

docnet and member 731016
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!

#### Attachments

• 1717043074935.png
14.7 KB · Views: 6
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.

member 731016

• Calculus and Beyond Homework Help
Replies
2
Views
894
• Calculus and Beyond Homework Help
Replies
6
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
436
• Calculus and Beyond Homework Help
Replies
13
Views
871
• Calculus and Beyond Homework Help
Replies
8
Views
1K
• Calculus and Beyond Homework Help
Replies
6
Views
603
• Calculus and Beyond Homework Help
Replies
5
Views
347
• Calculus and Beyond Homework Help
Replies
5
Views
663
• Calculus and Beyond Homework Help
Replies
7
Views
452
• Calculus and Beyond Homework Help
Replies
5
Views
652