3
$\begingroup$

I have a simple quadratic (with $x^2$) equation, x can Be complex too:

$$x^2+x+1=0$$

But it could be any equation, the equation above is just an example. I need to compute $x_1^{10}+x_2^{10}$, but it could have another exponents (ex: $x_1^{50}+x_2^{50}$).

I need to know, on a general case, how to find $x_1^n+x_2^n,\ n\in\mathbb{N}\ ax^2+bx+c=0,\ a\ is\ not\ 0$?

I ask this because I have to create a software which computes this (user writes the equation and the number n = exponent) and I can't find the roots always, because sometimes are complex. I think I should make use of Viete, but I don't know how to compute $x_1^n+x_2^n$.

Thank you very much!!

$\endgroup$
  • $\begingroup$ For the given first equation, $x$ is a complex cube root of unity $\endgroup$ – lab bhattacharjee Jul 15 '16 at 18:40
  • $\begingroup$ @labbhattacharjee Thank You! Please read the entire question. I am asking for computing $x_1^n+x_2^n$ on any quadratic equation. A method, other than finding roots. $\endgroup$ – MM PP Jul 15 '16 at 18:43
  • $\begingroup$ @MMPP why are you avoiding finding roots? $\endgroup$ – Mark Jul 15 '16 at 18:43
  • 2
    $\begingroup$ See en.wikipedia.org/wiki/Newton%27s_identities $\endgroup$ – lab bhattacharjee Jul 15 '16 at 18:45
  • 1
    $\begingroup$ You can convert the roots from the quadratic formula to polar form and then compute the powers that way. $\endgroup$ – arctic tern Jul 15 '16 at 19:08
5
$\begingroup$

One approach is to represent the roots in polar form, and take advantage of their symmetry. For the sake of ease of exposition, let the quadratic be monic; that is, $a = 1$. If it's not already in that form, it's trivial to convert it to a monic form.

If the roots are real—if $b^2-4c \geq 0$—I assume you know how to handle that. So we'll just consider the case where they're not real. In that case, $b^2-4c < 0$, and the roots are given by

$$ x_{1, 2} = \frac{-b \pm \sqrt{b^2-4c}}{2} = \frac{-b}{2} \pm \frac{\sqrt{4c-b^2}}{2}i $$

Note that $c > 0$ necessarily if the roots are not real. We can see, using the Pythagorean theorem, that $|x_1| = |x_2| = \sqrt{c}$. Now, find $\theta, 0 \leq \theta \leq \pi$ such that

$$ \cos\theta = -\frac{b}{2\sqrt{c}} $$ $$ \sin\theta = \sqrt{1-\frac{b^2}{4c}} $$

This can be done using the atan2 function in many programming languages. Then $x_{1, 2}$ can be represented as $\sqrt{c} \text{ cis } (\pm\theta) \equiv \sqrt{c} \left[\cos(\pm\theta)+i\sin(\pm\theta)\right]$. Then

$$ x_1^n = \sqrt{c^n} \text{ cis }(n \theta) $$ $$ x_2^n = \sqrt{c^n} \text{ cis } (-n\theta) $$

Since $x_1^n$ and $x_2^n$ form a conjugate pair (just as $x_1$ and $x_2$ do), we therefore have

$$ x_1^n+x_2^n = 2\sqrt{c^n}\cos (n\theta) $$

$\endgroup$
2
$\begingroup$

Newton-Girard's relations are very general, so we can redo the computations in the case of two roots.

Set $x+y= s; \enspace xy=p$. We want to compute recursively the sums of powers $$P_n=x^n+y^n$$ as polynomials in $s$ and $p$.

Initialisation:

$$P_0=2,\quad P_1=s=-1, \quad P_2=x^2+y^2=s^2-2p=-1.$$

Recursion relation: \begin{align*} P_{n+1}&=(x^n+y^n)(x+y)-x^ny-xy^n=(x^n+y^n)(x+y)-xy(x^{n-1}+y^{n-1})\\ &=sP_n-pP_{n-1}. \end{align*} Thus, \begin{align*} P_3&=sP_2-pP_1=s^3-3ps\\ P_4&=sP_3-pP_2=s^4-4ps^2+2p^2\\ P_5&=sP_4-sP_3=s^4-5ps^3+5p^2s\\ \&c.&\;\&c. \end{align*}

However, for this precise equation, we have $s=-1,\enspace p=1$ and the recursion relation becomes $$P_{n+1}=-(P_n+P_{n-1}),$$ so the computation is very simple: \begin{align*} P_0&=2,&P_1&=-1,&P_2&=-1,& P_3&=2,&P_4&=-1,&P_5&=-1.\end{align*} This is more than enough to see the sequence $(P_n)$ is periodic and that $$P_n=\begin{cases}2&\text{if}\enspace n\equiv 0\mod 3,\\ -1&\text{if}\enspace n\not\equiv 0\mod 3.\end{cases} $$ So the sums are $$x_1^{10}+x_2^{10}=x_1^{50}+x_2^{50}=-1.$$

$\endgroup$
  • $\begingroup$ It's simply $$x_{1}^{n}+x_{2}^{n}=\exp \frac{2n\pi i}{3}+\exp \frac{4n\pi i}{3}$$ $\endgroup$ – Ng Chung Tak Jul 17 '16 at 6:44
  • $\begingroup$ @Ng Chung Tak: You're absolutely right, but my point was to illustrate the use of Newton-Girard's relations in a very simple case $\endgroup$ – Bernard Jul 17 '16 at 9:26
1
$\begingroup$

\begin{align*} \alpha+\beta &= -\frac{b}{a} \\ \alpha \beta &= \frac{c}{a} \\ \alpha^n+\beta^n &= (\alpha+\beta)^{n}+\sum_{k=1}^{\left \lfloor \frac{n}{2} \right \rfloor} \binom{n-k}{k} \frac{n(-\alpha \beta)^{k} (\alpha+\beta)^{n-2k}}{n-k} \\ &= (\alpha+\beta)^{n}-n\alpha \beta (\alpha+\beta)^{n-2}+ \frac{n(n-3)}{2!} \alpha^2 \beta^2 (\alpha+\beta)^{n-4}-\ldots \\ \end{align*}

$\endgroup$

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.