1
$\begingroup$

Solving for $n$ in the equation $$\left ( \frac{1}{2} \right )^{n}+\left ( \frac{1}{4} \right )^{n}+\left ( \frac{3}{4} \right )^{n}=1$$

Can anyone show me a numerical method step-by-step to solve this? Thanks

$\endgroup$
12
  • 10
    $\begingroup$ LHS is strictly decreasing for all $n\in\Bbb R$, RHS is constant. $\lim_{n\to -\infty} \text{LHS}=+\infty$ and $\lim_{n\to +\infty} \text{LHS}=0^+$, so exactly one solution exists. $\endgroup$
    – user26486
    Jun 8, 2015 at 11:44
  • 4
    $\begingroup$ Writing this as $1^n+2^n+3^n=4^n$ is nicer (but does not directly help solving it). $\endgroup$
    – lhf
    Jun 8, 2015 at 12:14
  • 2
    $\begingroup$ Are you looking for solutions with $n$ an integer? $\endgroup$
    – lhf
    Jun 8, 2015 at 12:17
  • 3
    $\begingroup$ Do you have reason to believe that there is a closed form solution for $n$? Or will numeric methods suffice? $\endgroup$ Jun 8, 2015 at 12:20
  • 2
    $\begingroup$ There is no reason to think there is a closed form for this solution. Because $\log(3/4)$ and $\log(1/4)$ are incommensurable. $\endgroup$
    – GEdgar
    Jun 8, 2015 at 12:58

8 Answers 8

9
$\begingroup$

You seem to want the details of a numerical method to find an good approximation for $x$. Here is one way, using the Newton-Raphson method, which is well-known and uses fewer steps than other famous methods.

We want to find the zeros of

$$f(x)=0.25^x+0.5^x+0.75^x-1$$

(I rearranged the terms to be in ascending order, which satisfies my sense of style. I also changed the fractions to decimals to make it easier to type into a calculator.) We already know from comments and other answers that $x=1$ is too low and $x=2$ is too high. So let's choose the average, $1.5$, as our initial guess $x_0$. We then use the recurrence

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$$

This is what I typed into my graphing calculator (TI-Nspire CX):

$$x:=1.5$$ $$x:=x-\frac{0.25^x+0.5^x+0.75^x-1}{0.25^x\cdot\ln(0.25)+0.5^x\cdot\ln(0.5)+0.75^x\cdot\ln(0.75)}$$

That gave me the answer $$1.71161782284$$

which is $x_1$. Repeated presses of the [enter] key repeated the recurrence, and I got

$$1.73037816962$$ $$1.73050735181$$ $$1.73050735786$$ $$1.73050735786$$

More [enter]'s just repeated the last value. Therefore, an excellent approximation to your desired value, probably to $12$ significant digits, is $1.73050735786$.

$\endgroup$
13
  • $\begingroup$ Thank Rory - approx is good enough for government work! That's all I need. Many thanks $\endgroup$
    – James
    Jun 8, 2015 at 16:35
  • $\begingroup$ easy for me to write the code to - average, iteration - estimate. $\endgroup$
    – James
    Jun 8, 2015 at 17:02
  • $\begingroup$ @Rory Daulton It is necessary to prove that the sequence which is obtained from the Newton-Raphson method converges when $x_0 = 1.5$. $\endgroup$ Jun 8, 2015 at 20:47
  • $\begingroup$ @MathOverview: Who says a proof is necessary? Not the OP. I do know the proof of this, but I grant your point that the bisection method (for example) is much easier to prove as correctly convergent. $\endgroup$ Jun 8, 2015 at 20:53
  • 1
    $\begingroup$ @MathOverview You can see that it converges by trying it, so it is correct. A proof of convergence can be simplified since there is no extremum of $f$ in $[1,2]$. $\endgroup$
    – AlexR
    Jun 9, 2015 at 10:50
5
$\begingroup$

Let $f(x)=\left ( \frac{1}{2} \right )^{x}+\left ( \frac{1}{4} \right )^{x}+\left ( \frac{3}{4} \right )^{x}-1$. Now note that $f(1)=\frac12$ and $f(2)=-\frac18$. Hence given that $$f'(x)=-4^{-x}(3^x \log\frac43+2^x\log 2+\log4)<0$$ there is one unique root in $(1,2)$. The rest is numerics, this could be approximated to $1.73051$.

$\endgroup$
2
  • $\begingroup$ I have edited the question per the OP's following comments. The numerics is the subject of the question. $\endgroup$ Jun 8, 2015 at 16:42
  • $\begingroup$ @ChristopherA.Wong many thanks, I guess I am a bit late in fine-tuning my answer since there is another excellent and detailed answer to this by R. Daulton. $\endgroup$
    – Math-fun
    Jun 9, 2015 at 6:07
3
$\begingroup$

The function : $$y=0.25^x+0.5^x+0.75^x-1$$ is decreasing.

For example $y(1)=2$ and $y(2)=-\frac{1}{8}$. So, the root for $y=0$ is between $x=1$ and $x=2$.

In this case, among many numerical methods, the dichotomic method is very simple. The successives values $x_k$ are : $$x_{k+1}=x_{k}+\frac{\delta_k}{2^k}$$ where $\delta_k=\pm 1$

the signe is $+$ if $y_k=(0.25^{x_k}+0.5^{x_k}+0.75^{x_k}-1) >0$

the signe is $-$ if $y_k<0$.

ALGORITHM:

$x:=1$

$d:=1$

repeat

$ \quad \quad d:=\frac{d}{2}$

$ \quad \quad y:=0.25^x+0.5^x+0.75^x-1$

$ \quad \quad $ if $y>0$ then $x:=x+d$ else $x:=x-d$

until $d<10^{-15} $

(or another limit depending on the wanted accuracy).

RESULT : $x=1.73050735785763$

Of course, the convergence is slower than with the Newton-Raphson method for example. But, in both casses, the time of computation is so small that this is negligible. On the other hand, the time spent in programming the algorithm is smaller with the dichotomic method : that is the most important point in practice.

$\endgroup$
8
  • $\begingroup$ Thank you....much appreciated $\endgroup$
    – James
    Jun 8, 2015 at 16:54
  • $\begingroup$ "The time spent in programming" is negligible for Newton-Raphson if you do it on a calculator, as I did, at least if the derivative is easy (as in this case). And isn't your algorithm more commonly called the "Bisection method"? $\endgroup$ Jun 8, 2015 at 17:56
  • $\begingroup$ I agree with "bisection method". They are other terms : binary search or half-interval search. I don't know what name is the more appropriate. I will not argue about the time of programmation. This depends of the avalaible software. I also use commonly the Newton-Raphson or other methods depending of the cases. $\endgroup$
    – JJacquelin
    Jun 8, 2015 at 21:05
  • $\begingroup$ @JJacquelin Bisection method appears to be more standard in mathematical literature. (Binary search is more common in CS related topics and I've never heard of "dichotomic method") $\endgroup$
    – AlexR
    Jun 9, 2015 at 10:52
  • $\begingroup$ @ AlexR : OK. Thank you for the information. $\endgroup$
    – JJacquelin
    Jun 9, 2015 at 11:49
1
$\begingroup$

A non-standard approach to get an approximate solution:

Notice that the sum $$\frac14\left(\frac120.00^n+0.25^n+0.50^n+0.75^n+1.00^n\frac12\right)$$ is the five-points trapezoidal approximation of $$\int_0^1t^ndt=\frac1{n+1}.$$ So,

$$f(n)=0.25^n+0.50^n+0.75^n\approx\frac4{n+1}-\frac12.$$ Hence, $f(n)=1$ when $$n\approx\frac53=1.66666\cdots.$$ Note that $$f(\frac53)=1.033304\cdots,$$not so bad.

$\endgroup$
1
  • $\begingroup$ This is indeed an intereting use of the trapezoidal method ! $\endgroup$ Jun 10, 2015 at 8:54
0
$\begingroup$

There is no analytic solution for this problem. However, the LHS is monotonic, and as such easy to solve numerically using your method of choice.

$\endgroup$
1
  • $\begingroup$ I have edited the question per the OP's following comments. The numerics is the subject of the question. $\endgroup$ Jun 8, 2015 at 16:42
0
$\begingroup$

Classic problem for Newton's Method.

Note that $F(n) = \dfrac{1}{2^n} + \dfrac{1}{4^n} + \dfrac{3^n}{4^n}-1$ is continuously differentiable. Furthermore, $F(0) = 2$ and $\lim_{n \rightarrow \infty} F(n) =-1$ so by the Intermediate Value Theorem, there is definitely a zero.

I used Maple to calculate the root to a tolerance of $10^{-15}$ because I can.

with(Student[NumericalAnalysis]):
F(z):= n-> 1/2^n + 1/4^n + 3^n/4^n:


Newton(F(z),n=0.2,tolerance=10^-15)
>>>1.73050735785764
$\endgroup$
0
$\begingroup$

As other answers already mentioned, we can notice that $f(1)=\frac12$ and $f(2)=-\frac18$ which mean that, more than likely, the solution is rather close to $x_0=2$. If we start Newton method at this point, the successive iterates are $$x_1=1.703616841$$ $$x_2=1.730245725$$ $$x_3=1.730507333$$ $$x_4=1.730507358$$ which is the solution for ten significant figures. You can notice that we have one overshoot of the solution because the iterations started at a point $x_0$ for which $f(x_0)f''(x_0) <0$.

It can be woth to mention that the convergence to the solution could be faster using higher order iterative methods. For example, starting at $x_0=2$, using Halley method (cubic convergence) the first iterate would be $1.733482269$ while using Householder method (quartic convergence) the first iterate would be $1.730170949$.

Edit

As Peter answered , the problem could be reset as $$f(x)=4^x-(1+2^x+3^x)$$ which is a very stiff function. However, if we consider instead $$g(x)=x\log(4)-\log(1+2^x+3^x)$$ the function is much more linear. Starting again Newton method at $x_0=2$, the successive iterates will now be $$x_1=1.722964808$$ $$x_2=1.730501219$$ $$x_3=1.730507358$$

You could also be interested by the fact that, expanding $g(x)$ as a Taylor series built at $x=2$ and limiting to second order, the solution of the quadratic equation gives an estimate which is $\approx 1.730171694 $.

$\endgroup$
2
  • $\begingroup$ a typical answer of yours :) $\endgroup$
    – user65203
    Jun 9, 2015 at 13:06
  • $\begingroup$ @YvesDaoust. I am really afraid that this is true ! Cheers :) $\endgroup$ Jun 9, 2015 at 16:26
-1
$\begingroup$

$\left ( \frac{1}{2} \right )^{n}+\left ( \frac{1}{4} \right )^{n}+\left ( \frac{3}{4} \right )^{n}= \frac{2^n}{4^n} +\frac{1^n}{4^n} +\frac{3^n}{4^n} = \frac{1^n+2^n+3^n}{4^n}=1,\: \therefore 1^n+2^n+3^n=4^n $

I don't think this can be solved analytically, you just have to use trial and error with n

$\endgroup$
1
  • $\begingroup$ Thanks for that - however, that's a problem as I wanted to code an algo to do it.....maybe there is a way. $\endgroup$
    – James
    Jun 8, 2015 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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