How come some equations can't be solved for an exact answer?

[Borek]

$$R=\sum_{k=1}^\infty10^{-k}r_k$$ with $r_1=3,r_2=3,r_3=5,r_4=4,r_5=1,r_6=8,r_7=0,r_8=3,\ldots.$

Apples and oranges.

 

[Borek]

Which shows that you misunderstood my post, since it looks like you have just solved the equation with a calculator and defined a sequence {rk} being the decimal expansion, right?

My question was, if you can find a solution on the form

$$\sum_{k=1}^{\infty} f(k,x)$$ where f is a function composed of elementary functions (or better, only polynomials), or maybe including more airthmetic/geometric sums of elementary functions.

Sum posted is already a polynomial

 

[Borek]

Arrgh, I can't edit anything, even quoting doesn't work now for me :( Neither in Opera nor in IE.

Kurret: you must concentrate on defining EXACTLY what you mean. I believe most people here understand what you are aiming at, but so far they had no problems with showing that intuition fails here. As long as you will not precisely define what is allowed in the expression you are looking for, you are on the lost position.

 

[Kurret]

Arrgh, I can't edit anything, even quoting doesn't work now for me :( Neither in Opera nor in IE.

Kurret: you must concentrate on defining EXACTLY what you mean. I believe most people here understand what you are aiming at, but so far they had no problems with showing that intuition fails here. As long as you will not precisely define what is allowed in the expression you are looking for, you are on the lost position.

Im sorry but i don't know how I can define it better. The sum posted is not a polynomial, its a sum of an already defined sequence of numbers, the terms in the sequence isn't a function.

I realize now that the x in the function should not be there, the sum should be
$$\sum_{k=1}^\infty f(k)$$
ie, every term in the sum should be equal except that k varies.

 

[CRGreathouse]

How do you generate the $$r_n$$'s?

I actually used the secant method, but for your purpose let's say I used bisection. It's easy to see that four steps of the bisection method are enough to guarantee a decimal digit, so the procedure always generates correct answers.

Actually, since the method brackets the root, you can tell when you have enough to determine a decimal digit.

 

[CRGreathouse]

My question was, if you can find a solution on the form

$$\sum_{k=1}^{\infty} f(k,x)$$ where f is a function composed of elementary functions (or better, only polynomials), or maybe including more airthmetic/geometric sums of elementary functions.

But they are. f(1, x) is a very simple combination of elementary functions $3\cdot2^k$.

 

[DavidWhitbeck]

Kurret if f is a polynomial with nonzero coefficients then your series will be divergent, because the sequence of terms does not converge to zero.

For example if $$f(k)=k^2$$ then $$\lim_{k->\infty}f(k) \neq 0$$.

This means that the answer to your question is no because solutions to equations if they exist are not represented by divergent series. That is in response to you asking if you can represent solutions to equations by series of polynomials. Non-polynomial represents such as those shown by CRGReathouse are a different story.

 

[Kurret]

But they are. f(1, x) is a very simple combination of elementary functions $3\cdot2^k$.

I don't get this
All terms should be the same function, right? Or do I completely misunderstand what you mean?

 

[Kurret]

dbl post, sry

 

[Kurret]

I can give an example. let's say we try to find the solution to xe^x=7. The inverse of xe^x is the so called lambert w-function, so if xe^x=7, then w(7)=x. According to http://mathworld.wolfram.com/LambertW-Function.html
we have the series expansion of w(y) being:
$$w(y)=\sum_{n=1}^\infty {\frac{(-1)^{n-1}n^{n-2}}{(n-1)!}y^n}$$
thus the solution to xe^x=7 is:
$$w(7)=\sum_{n=1}^\infty {\frac{(-1)^{n-1}n^{n-2}}{(n-1)!}7^n}$$
so, is it possible to solve any function using this method, ie finding the infinite sum representation of the inverse?

 

[DavidWhitbeck]

Kurret that is not an example of what you said though-- the terms are not a polynomial in n. If you want the coefficients in your series to be represented by any map from N to Q then certainly the decimal expansion is just as acceptable.

I think it's time for you to rephrase what you mean. I'm having a hard time understanding what you're asking since you seem to be inconsistent about it, and I doubt I'm alone in that regard.

 

[CRGreathouse]

I don't get this
All terms should be the same function, right? Or do I completely misunderstand what you mean?

Perhaps you don't understand what is meant by function. f(1) = 0.3, f(2) = 0.03, etc. is a perfectly good function on k.But regardless, consider this. Let $h(x)=\sin x+2x-1$, $g(0)=0$,
$$g(k)=10^{-k}\cdot\sum_{i=0}^{10^k}\frac{h(i/10^k)-|h(i/10^k)|}{2|h(i/10^k)|}$$
for k > 0, and
$$f=\sum_{k=1}^\infty g(k)-g(k-1)$$.

f is the root of your equation. A variant on this formula would find the root to most any continuous function. But bisection would give an exponential speedup over a direct implementation of this formula, and the secant method a polynomial speedup on top of that.

 

[Kurret]

Kurret that is not an example of what you said though-- the terms are not a polynomial in n. If you want the coefficients in your series to be represented by any map from N to R then certainly the decimal expansion is just as acceptable.

I think it's time for you to rephrase what you mean. I'm having a hard time understanding what you're asking since you seem to be inconsistent about it, and I doubt I'm alone in that regard.

Yes I agree on that. You showed a good example of why it isn't possible with polynomials, so that question is now answered. So now, let's consider all elementary functions, which that clearly is (the factorial is a geometric sum of the elementary function f(x)=x).

 

[Kurret]

CRgreatHouse, I think that is something like the answer I was looking for :). Nice!
Can you explain a bit furthermore why it does work, ie a non math/geometric explanation? :p can't really understand that atm.

 

[CRGreathouse]

(CRGreathouse = C. R. Greathouse)

CRgreatHouse, I think that is something like the answer I was looking for :). Nice!
Can you explain a bit furthermore why it does work, ie a non math/geometric explanation? :p can't really understand that atm.

I can explain, sure, but remember that the form is entirely worthless.

Consider the following algorithm. Choose a neighborhood and a function so that the function has only one zero in the neighborhood, is negative to the left of the zero, and positive to the right of the zero. (For an equation a(x) = b(x), this could be a(x) - b(x) or b(x) - a(x).) You can then split the neighborhood into a finite number of evenly-spaced intervals and see if the value of the function is negative or positive. If there are n negative values and t - n positive values, the function has its zero (and so the equation has its root) between n / t * (b - a) + a and (n + 1) / t * (b - a) + a, where a is the left and b the right of the neighborhood.

This is just a really bad version of bisection. My formula is just the equation form of this process. h(x) is the function, and the neighborhood is [0, 1]. The root is
$$\lim_{k\to\infty}g(k)$$
but since you weren't allowing limits I defined f in a way that gives the limit as an infinite sum.

You can see that this method is similar to computing integrals by counting progressively-finer grid squares.

 

[mathwonk]

let me pose a simple question. do you think pi has an exact value? if so, what is it?let me make it easier for you, what is the exact value of sqrt(2)?

if you think about it you may realize I am trying to discern what is your definition of the phrase "exact answer".

by the way matt, i understand that you are busy, but i still convey to you the fact that many people including me miss you here a great deal, and there is a whole, thread called "where is matt grime?!"

 

[LukeD]

As to this exact question, I don't know if there is any "simple formula" that would be close to what you mean, but sometimes there are.

For instance, for pi, there is
$$\pi=3 + \cfrac{1}{6 + \cfrac{9}{6 + \cfrac{25}{6 + \cfrac{49}{6 + \cfrac{81}{6 + \cfrac{121}{\ddots\,}}}}}}$$(taken from Wikipedia's article on continued fractions)

The functions in the formula you're asking about having an exact solution do have nice formulas of the sort you want, so it might be that your question might have a formula of that sort.

However, in general, no one knows if there is a "nice formula" for your problem. And really, the only reason for that is because either no one has yet figured one out or no one has been trying to find one. I don't know if it's the case that every real number will be able to written in some nice formula though.

 

[CGUE]

To 500 places:
0.3354180323849400594578624117492548397118513151006308650233458056997707969
93488867326823297805099655941760946007417735305449140296885174971232582467743747
67817725202600726615999809586989494215709825435975337739655562116739626518112856
23055310151600910291959720327473494910708608367675240373868492976882512228069498
07934021595150112613380719098738548853419012578533010207808040687825471704745279
60925128393175327764000215850832461166054705141754704841341722301915669142357206
871814814939461336135943871

Haha win, don't we all love Mathematics Computing Packages ?
(Or Biological geniuses by a slim chance if you calculated that in your head?)

Maple 11 output:

>Digits:=500;

Digits := 500

> fsolve(2*x+sin(x)=1);

0.33541803238494005945786241174925483971185131510063086502334580\
5699770796993488867326823297805099655941760946007417735305\
4491402968851749712325824677437476781772520260072661599980\
9586989494215709825435975337739655562116739626518112856230\
5531015160091029195972032747349491070860836767524037386849\
2976882512228069498079340215951501126133807190987385488534\
1901257853301020780804068782547170474527960925128393175327\
7640002158508324611660547051417547048413417223019156691423\
57206871814814939461336135943871

I should have asked my friend to go solve an equation like this in a computing package like this instead of asking me in the middle of a lecture.

 

[CRGreathouse]

However, in general, no one knows if there is a "nice formula" for your problem. And really, the only reason for that is because either no one has yet figured one out or no one has been trying to find one. I don't know if it's the case that every real number will be able to written in some nice formula though.

It's awfully hard to determine if there's a nice formula without a working definition for "nice formula". :)

But a simple counting argument will show that almost all real numbers have no formula, where for a given finite set of symbols (0, 1, +, -, *, /, etc.) a "formula" is some subset of the finite strings of those symbols.

 

[CRGreathouse]

Haha win, don't we all love Mathematics Computing Packages?

Yep. This one was a custom implementation of the secant method in Pari (v. 2.4.2; won't work in 2.3.x unless you remove ff from the variable list and predefine it):

secant_root(ff, first, second)={
	local(ff1, ff2, oldfirst, ep);
	ff2 = ff(second);
	ep = 2 * eps();
	while (abs(first - second) > ep,
		ff1 = ff(first);
		oldfirst = first;
		first = first - (first - second) / (ff1 - ff2) * ff1;
		second = oldfirst;
		ff2 = ff1;
	);
	first
}

\\ 2 ^ -(decimal_precision * log(10)/log (2) / 32) * 32 - 1)
eps()={
	precision(2. >> (32 * ceil(precision(1.) * 0.103810252965230073370947482171543443)), 9)
}

I also have bisection, Newton's method, and Halley's method, but these are slower for this problem (and probably slower is most cases). Higher-order convergence isn't all it's cracked up to be when it means you need to calculate more functions!

 

[mathwonk]

NOW THAT YOU have defined an exact answer as a limit of a nice sequence, we ought to take a vote on how many think the usually convergent sequence arising from Newton's method is nice enough to qualify.