# Algebraic shortcut to find $a^n + b ^n$?

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

• 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)$. Apr 10, 2016 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. Apr 10, 2016 at 21:00

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.

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