Maths / Compsci help

[Pezzoni]

I've run into a slight homework problem this evening:



I can't think of a way to get a suitable c2, it obviously needs to be >= 5n+40, but any constant will surely become too small for a sufficiently large n? Any ideas of how I should be approaching this?

Thanks,

[Darth Holbytlan]

I can't think of a way to get a suitable c2, it obviously needs to be >= 5n+40, but any constant will surely become too small for a sufficiently large n? Any ideas of how I should be approaching this?

This is incorrect. You need to work straight from your equations. Solve for c_2 from c_2*7^n >= 7^n + 5n + 50. Then pick a c_2 that fits that.

[Kuroneko]

Also, remember that it doesn't need to hold for all n, but only n≥n_0. Since lim_{n→∞}[ f(n)/g(n) ] = 1, any c_2>1 will work if n_0 is large enough. If you write the bounding condition as c_2≥f(n)/g(n), wherever g is positive, and simplify, this may become more obvious.

[Xenophobe3691]

Hm, breaking it down:

Taking the limit as n -> Infinity, the 7^n term blows up enormously faster than the rest of the terms in f(x). Just look at this chart:

Code: Select all

n      7^n              7^n + 5n + 40
---------------------------------
1        7                         52
2        49                       99
3        343                     398
4        2401                   2461

You can just multiply 7^n it by any number greater than 1, and you'll eventually surpass f(x). I'd use 2, just for the sake of using a whole number.

[Xenophobe3691]

ARGH, Kuroneko beat me to it. Ah well

[Pezzoni]

Thanks everyone; does this look like a reasonable (from a justification point of view) answer?

[fnord]

That looks good, but if you're using n0 = 1, you can tighten that upper bound somewhat.

As Kuroneko said, f(n) / g(n) may give some insights, namely:

f(n) / g(n) = (7^n + 5n + 40) / 7^n = 1 + (5n + 40)/7^n

Since you're using n0 = 1,
f(1) / g(1) = 52 / 7 = 7.428... < 7.43

[Darth Holbytlan]

I was trying to avoid simply handing out an answer, but that seems to be moot now. So, yeah, f(n)/g(n) is where I was going with that:

c_2*7^n >= 7^n + 5n + 40
c_2 >= 1 + (5n + 40)/7^n

Since lim_{n→∞} 1 + (5n + 40)/7^n = 1, we know that for any c_2 > 1, there exists an n_0 such that for all n >= n_0, c_2 > 1 + (5n + 40)/7^n. (Definition of limit)

Since any reasonable c_2 will work, you don't really need to find a particular one. Proving that one exists is good enough.

[Pezzoni]

Thanks to both of you - I've read through your answers and understand them.

I'm going to stick with mine on the basis that it's more my own work (and still fulfils the definition with a reasonable justification (I think?)), though I know it could be 'tighter'.

Thanks again