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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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$

Answer 4

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

Answer 5

$$\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)$