5

Recently, I found this problem online:

Given $a+b=1$ and $a^2+b^2=2$, find $a^7+b^7$.

Although I could've solved it by substituting the first equation into the second and then using the quadratic formula; the way the question was set up, I suspected that there was a shortcut. However, I couldn't find the solution to the problem on that website, so I'm asking here:

If you are given $a+b$ and $a^2+b^2$, is there a shortcut to finding $a^n+b^n$?

Shuri2060
  • 4,353
  • 3
    From $a^2+b^2=(a+b)^2-2ab$ we can obtain $ab$. Now, since $a+b$ and $ab$ are elementary symmetric polynomials, any other symmetric polynomial in variables $a$ and $b$ can be expressed using these two. However, I doubt that there will be a nice formula. You can start from $a^n+b^n=(a+b)^n-(nab(a^{n-2} + b^{n-2}) + \frac{n(n-1)}{2}a^2b^2(a^{n-4}+b^{n-4}) + \dots)$. – lisyarus Apr 10 '16 at 21:00
  • Not really a shortcut, but you can square $a+b=1$ to get $a^2+2ab+b^2=1$ and by substitution, $ab=-\frac{1}{2}$. Then, you might have some luck with an induction and the binomial theorem, but I don't think that there's much help here. – Michael Burr Apr 10 '16 at 21:00

1 Answers1

12

Note that $$a^{n+1}+b^{n+1}=(a^n+b^n)(a+b)-ab(a^{n-1}+b^{n-1}).\tag{1}$$ Since $(a+b)^2=1$, and $a^2+b^2=2$, we have $2ab=-1$ and therefore $ab=-\frac{1}{2}$.

It follows from (1) that $$a^{n+1}+b^{n+1}=(a^n+b^n)(1)+\frac{1}{2}(a^{n-1}+b^{n-1}).$$

Let $f(k)=a^k+b^k$. We have obtained the recurrence $$f(n+1)=f(n)+\frac{1}{2}f(n-1).$$ Using this recurrence, we can compute our way to $f(7)$ fairly quickly.

Remarks: $1.$ The same strategy can be used for any given $a+b$ and $a^2+b^2$.

$2.$ To go a little faster, we could use $a^{n+2}+b^{n+2}=(a^n+b^n)(a^2+b^2)-a^2b^2(a^{n-2}+b^{n-2})$.

$3.$ If we are in a real hurry, and $n$ is not small, there are various tricks to speed up computation. For example $$a^{2k}+b^{2k}=(a^k+b^k)^2-2(ab)^k.$$ So we can take "giant" steps.

André Nicolas
  • 507,029