Proof by induction for rational function

  • #1
member 731016
Homework Statement
Please see below
Relevant Equations
Please see below
For this problem,
1716848580326.png

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!
 
Physics news on Phys.org
  • #2
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##?
 
  • Like
  • Love
Likes docnet and member 731016
  • #3
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##?
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!
 
  • #4
ChiralSuperfields said:
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?

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.

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*}
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.
 
  • Like
  • Love
Likes docnet and member 731016
  • #5
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.
 
  • Like
  • Love
Likes docnet and member 731016
  • #6
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}}##.
 
  • Love
Likes member 731016
  • #7
Thank you for your replies @fresh_42 and @WWGD!

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

1717043196192.png


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
    1717043074935.png
    14.7 KB · Views: 6
  • Like
Likes docnet
  • #8
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.
 
  • Love
Likes member 731016

Similar threads

  • 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
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
Back
Top