Proving a^n/p(n) Tends to Infinity with n

[dichotomy]

i've to show (as part of a bigger assignment) that

a^n/p(n), where p is any polynomial and a>1, tends to infinity as n does. I've proved that:

a^n/n^k

does so, but I'm not sure how to extend this to a complete polynomial such as

(c1)n+(c2)n^2+(c3)n^3...

thanks for any help

NB: edited

 

[matt grime]

You've used a for two different things; and forgotton a condition on the first a.

Remember the triangle inequality:

|x+y| <= |x|+|y|

that will help.

 

[dichotomy]

right...well all i can think of at the moment is changing (n^k) to (n+b)^k and prove that it works for that - however i don't think that's valid since (i don't think) every possible polynomial can be created by such an expansion.

i've not a clue where to start with the triangle inequality

 

[StatusX]

Try proving the reciprical tends to zero, then you can just add different powers of n in the numerator.

 

[dichotomy]

proving the reciprocal goes to zero is exactly how i did a^n/n^k...

but i didn't think you could just add terms in various powers of n and expect the same result as a^n/n^k (or its reciprocal) without proving it?

 

[dichotomy]

also, i think all that is needed is the ratio test for convergence (of the reciprocal) however if I use this when I replace n^k with (b+n)^k (to create the polynomial), i end up with series within series, and I'm not sure what to do with that.

(The ratio test is also what i used for a^n/n^k)

 

[Gib Z]

The nth root test, where you take the nth root as n approaches infinity.

For the numerator, you get (a^n)^(1/n) as n approaches infinity. The powers equate leaving us with just a. The denominator, it becomes p(n)^(1/n) as n approaches infinity. so in the end we get a*p(n)^n. As n approaches infinity, the polynomial will as well. So the result of our nth root test is more than 1. That means it does not converge, and therefore diverges. As n approaches inifinity, both a^n and p(n)^n will be positive, meaning it diverges positively, to infinity.

Note: I didnt use that triangle inequality that matt grime posted, which makes me think i may have done something wrong lol, matt grimes always right...

 

[matt grime]

There is always more than one way to skin cat. However, you have asserted that

a/p(n)^{1/n} = a*p(n)^n

which is not correct. Your 'proof' also works for a=1, which is unfortunate, as 1/p(n) tends to zero as n tends to infinity.

 

[matt grime]

The hint was to use the triangle inequality. I don't see anyone doing that. Try to use the triangle inequality to go from studying p(n) to a k*n^r, where k is a constant and r is the degree of p(n) (and no, k is not the coeffeicient of n^r in p(n)).

 

[matt grime]

proving the reciprocal goes to zero is exactly how i did a^n/n^k...

but i didn't think you could just add terms in various powers of n and expect the same result as a^n/n^k (or its reciprocal) without proving it?

That is what the triangle inequality will let you do - You can replace

$$| b_r n^r + b_{r-1}n^{r-1} + \ldots b_0|$$

with something larger. Notice that n^r > n^{r-1} for n>1, r>2.

 

[dichotomy]

do you mean:

$$| b_r n^r + b_{r-1}n^{r-1} + \ldots b_0| \leq |n^r + n^r + n^r + \ldots \mbox{(to the extent of k)}|$$

which only is true if

$$b_{r-s} < n^s \mbox{ and } \ k=r$$ where s=1,2,3...

but the coefficients of $$n^{r-s}$$ are going to be much smaller than any possible value of $$n^{r-s}$$ once n approaches infinity, such that the first condition can be ignored?

nb: only just started with latex so bear with me...

 

[matt grime]

What are you using k to mean? Not what I used it to mean.

 

[Gib Z]

ahh damn i knew i must have stuffed something up, couldn't have been that simple that someone else didnt see...ahh o well

 

[Werg22]

You are talking about orders of magnitude. First, we prove that a^x/ x tends to infinity as x increases beyond all bounds. Consider the function f(x) = log [a^x/ x] = x log a - log x. Surly if we prove that if f(x) goes to infinity, we prove that a^x/ x goes to infinity as well. Now let us consider f'(x) = log a - 1/x. Now for x>c, we have f'(x)>1/2 log a. Let us define g'(x) = 1/2 log a. By the principles of integral,

f(x) - f(c) > g(x) - g(c).f(x) - f(c) > (x-c)*1/2 log a

f(x) > (x-c)*1/2 log a + f(c)

Clearly the right expression goes to infinity as x increases. Thus we have proved that f(x) goes to infinity as well.

Now we have a polynomial of power n and a x^n+1. If p(x) remains positive past a certain point, the expression x^n+1/p(x) goes to infinity - this can be proven using Hopital's law. Now

a^x/p(x) = [a^x/x^n+1]*[x^n+1/p(x)].

We need only to prove that a^x/x^n+1 has a positive limit or is unbounded in order to prove the statement that a^x/p(x) goes to infinity as x increases. We consider, the n+1 th root of the expression that is,

a^x/n+1 / x

This can be rewritten as

1/n+1 * [a^x/n+1 / (x/n+1)]

Putting x/n+1 = y, we have

1/n+1 * [a^y / y]

As was shown, a^y/y goes to infinity as y increases. Thus, the n+1 th root goes to infinity and a^x/x^n+1 goes to infinity as well. Finally, a^x/p(x) goes to infinity.