5
$\begingroup$

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$?

$\endgroup$
2
  • 3
    $\begingroup$ 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)$. $\endgroup$
    – lisyarus
    Apr 10, 2016 at 21:00
  • $\begingroup$ 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. $\endgroup$ Apr 10, 2016 at 21:00

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ And in general, $$f(n+1) = f(n) f(1) - \frac{f(n-1)(f(1)^2-f(2))}{2}$$ $\endgroup$ Apr 10, 2016 at 21:12
  • $\begingroup$ Andre, it is $f(n+1) = f(n) + \frac{1}{2} f(n-1)$ $\endgroup$
    – Will Jagy
    Apr 10, 2016 at 21:19
  • 1
    $\begingroup$ @WillJagy: Thanks, I have trouble with minus signs. One is usually OK, two or more not so much. $\endgroup$ Apr 10, 2016 at 21:22
  • $\begingroup$ @QuestionAsker: Thanks, fixed. $\endgroup$ Apr 10, 2016 at 21:24
  • $\begingroup$ The displayed equation after "It follows from (1)" should also have $+\frac{1}{2}$ instead of minus. $\endgroup$
    – Will Jagy
    Apr 10, 2016 at 21:27

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.