# A nonlinear single variable equation

Say I have $f(k)$ for all $k = 1, \ldots, 2^n$, and $0\le f(k)\le n$.

I would like to solve for $x$:

$$x\sum _{k=1}^{2^n }\frac{1}{f(k)+x} =1.$$

And also this if possible,

$$\sum _{k=1}^{2^{n} }\exp\left(\frac{-f(k)^{2} }{x} \right) =1.$$

Any ideas?

-
Don't you have any more information you can give on your $f(k)$? –  Guess who it is. Jul 20 '11 at 11:23
I can, but I don't think it will help... f(k) is a (normalized) distance measure from a vertex (indexed by k) of a unit hypercube of dimension n to a certain point within the hypercube. So it can range from 0 to n (since the metric is Manhattan). Helps...? –  Omri Jul 20 '11 at 11:31
Leaving $f(k)$ unspecified is certainly less helpful than the information you gave. :) –  Guess who it is. Jul 20 '11 at 11:33
Both are well-behaved functions of $x$, so a one-dimensional root finder should have no trouble returning a numeric solution. –  Ross Millikan Jul 20 '11 at 14:19

Solving the second is equivalent to solving for $y$:

$$\sum_{k=1}^{M} \exp(- a_k y ) = 1$$

for some given $M=2^n$, $a_k = f(k)^2$ (so $0 \le a_k \le n^2$), and $x = 1/y$ This is obviously not solvable analytically, but (as Felix points out) it's a nice function, smooth and decreasing, it have a single solution and it's easy to find numerically. Little more can be said withouth knowing $a_k$

-
Thanks, leonbloy and @FelixCQ. One more point - notice that there are an exponential (in n) number of summands. Thus for high n it becomes very hard to solve - is there any way to approximate a solution for x in this case, while avoiding exponential time? –  Omri Aug 10 '11 at 15:22
@Omri: As long as you don't put any other restrictions on $a_k$, my equation is exactly as general as yours. Hence, I have $M$ summands (as many as $a_k$ coefficients ; I don't mind if $M=2^n$ or whatever; you can forget about it). You cannot expect some approximation if you don't know anything about $a_k$. –  leonbloy Aug 10 '11 at 15:47

Multiplying both sides of the first equation by

$$\prod_{k=1}^{2^n} \big( f(k) + x\big)$$

reveals that solving your equation is equivalent to solving a polynomial of degree $2^n$, which is possible analytically for $n=0$, $n=1$ and $n=2$, but not in general for $n\geq 3$, unless your coefficients $f(k)$ have a particularly nice form.

-
Thanks, Chris. Any idea about the second equation? –  Omri Jul 20 '11 at 12:33

About the second equation, it seems a solution exists for a unique positive $x$.

Solutions cannot be negative, since the left hand side would be bigger than $2^n$.

On $\mathbb{R}_+$, whe have:

• The left hand side is a sum of increasing functions, so it is itself increasing.
• Letting $x$ go to $0$, the left hand side goes to $0$.
• Letting $x$ go to infinity, the left hand side goes to $2^n > 1$.

So there is a unique value in between that solves the equation, but I don't see how to solve it analytically.

Given its monotonic nature, it should be very easy to solve numerically, with a Newton-Raphson method, for example.

-