Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Don't you have any more information you can give on your $f(k)$? –  J. M. 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. :) –  J. M. 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
add comment

3 Answers

up vote 1 down vote accepted

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$

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Thanks, Chris. Any idea about the second equation? –  Omri Jul 20 '11 at 12:33
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.