Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
For generalizations (and some other related theory) look up Newton's identities. –  Jyrki Lahtonen Mar 5 '13 at 10:15
add comment

5 Answers

up vote 10 down vote accepted

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

share|improve this answer
add comment

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$

share|improve this answer
add comment

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.

share|improve this answer
2  
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
add comment

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

share|improve this answer
1  
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.