How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?

I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it?

I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ might be as large as $10^9$. Then I have to calculate the last 10 digits only.

NB: I've found this problem in the category of Matrix Exponentiation.

-
For generalizations (and some other related theory) look up Newton's identities. – Jyrki Lahtonen Mar 5 '13 at 10:15

Call $s=a+b$, $p=ab$, and $s_n=a^n+b^n$ for every $n\geqslant0$, then $ss_n=s_{n+1}+ps_{n-1}$ for every $n\geqslant1$ hence one can compute recursively $(s_n)_{n\geqslant0}$ using $$s_0=2\qquad s_1=s\qquad s_{n+1}=ss_n-ps_{n-1}\ (n\geqslant1).$$ Alternatively, the vectors $v_n=(s_n,s_{n-1})$ are such that $v_{n+1}=v_nM$, where $M=\begin{pmatrix}s & 1 \\ -p & 0\end{pmatrix}$, hence $v_n=(s,2)M^{n-1}$ for every $n\geqslant1$, that is, if $M^k=\begin{pmatrix}x_k & y_k \\ z_k & t_k\end{pmatrix}$, then $s_n=sx_{n-1}+2z_{n-1}$ or $s_n=sy_n+2t_n$.

-

Consider the diagonal matrix $M = \begin{pmatrix} a & 0 \\ 0 & b\end{pmatrix}$.

You know its trace $a+b$ and determinant $ab$, so you know its minimal polynomial $M^2-(a+b)M+ab$.

You want to find $tr(M^n)$. Since the trace is linear, the sequence $(t_n = tr(M^n))$ satisfies the same recurrence linear relation as $M$ : $t_{n+2} = (a+b). tr_{n+1} - ab. t_n$

Now, consider $X_n = \begin{pmatrix}t_n \\ t_{n+1} \end{pmatrix}$. You find that $X_{n+1} = \begin{pmatrix} 0 & 1 \\ -ab & a+b\end{pmatrix} X_n$. Since $X_0 = \begin{pmatrix}2 \\ a+b \end{pmatrix}$, you obtain $X_n = \begin{pmatrix} 0 & 1 \\ -ab & a+b\end{pmatrix}^n \begin{pmatrix}2 \\ a+b \end{pmatrix}$.

Now, this is a matrix you actually know, so you can compute its $n$th power (use binary exponentiation to be fast), apply it to $X_0$, and read the first coordinate to obtain $t_n$

-

I think the best way is to just use $a+b$ and $ab$ (2 equations 2 unknowns) to find out what $a$ and $b$ are and then just take their powers.

-
Hmm. Nothing wrong with this in theory, but there is a point that you may not have fully appreciated. Let's say that you figure out that $a=2+\sqrt3$ and $b=2-\sqrt3$. You know that $a^{100}+b^{100}$ is an integer, and you want to know it exactly. Now what? – Jyrki Lahtonen Mar 5 '13 at 10:18
@Jyrki it is still conceptually the same, but would require a number extension similar to the complex numbers, using $\sqrt{3}$ instead og $\sqrt{-1}$. Which of course is just a way of extending things to two dimensions but with avoiding matrices. So I agree with your point but also with Fixed Point's point. – adam W Mar 5 '13 at 17:36

Solution 1 (this is the same recurrence Did provided)

If $n=0$, then $a^0+b^0=2.$

If $n=1$, then $a^1+b^1=a+b$, a value you know.

If $n\geq 2$, then $a^n+b^n=(a+b)(a^{n-1}+b^{n-1})-ab(a^{n-2}+b^{n-2})$, which you can compute recursively using the known values for $a+b$ and $ab$.

Solution 2 (inspired by mercio's answer)

Since you know $a+b$ and $ab$ you can find the roots of the polynomial $x^2-(a+b)x+ab$, which are precisely $a$ and $b$. Now, since you also know $n$, you can compute $a^n+b^n$.

-
Hm, it looks similar to the answer by Did. – awllower Mar 5 '13 at 10:12
Indeed, it's the same recurrence. – A. Bellmunt Mar 5 '13 at 10:14

$$\text{ We know, }(a+b)^n=a^n+\binom n1a^{n-1}b+\binom n2a^{n-2}b^2+\cdots+\binom n{n-2}a^2b^{n-2}+\binom n{n-1}ab^{n-1}+b^n$$

$$\text {So, }a^n+b^n=(a+b)^n-\binom n1 ab(a^{n-2}+b^{n-2})-\binom n2(ab)^2(a^{n-4}+b^{n-4})-\cdots$$

If $F_n=a^n+b^n,F_n=(a+b)^n-\binom n1abF_{n-2}-\binom n2(ab)^2F_{n-4}-\cdots$

This approach should require lesser iteration as we don't need to calculate $F_{n-1},F_{n-3},F_{n-5}$ etc.

If $n$ is even $=2m$(say), the last term will be $\binom{2m}m(ab)^m$

If $n$ is odd $=2m+1$(say), the last term will be $\binom{2m+1}ma^{m+1}b^m+\binom{2m+1}{m+1}a^mb^{m+1}=\binom{2m+1}m(ab)^m(a+b)$

-
Actually we don't need to iterate up to n to find $f_n$. According to Did's answer we get a recurrence that needs only the n-1 exponential of matrix M. We can do this in order of $dimention^3*log(n)$ – mostafiz Mar 5 '13 at 15:14