Question

What is the value of (ab)n? aⁿbⁿ abⁿ aⁿb

Answer 1

Answer:

Call s=a+b, p=ab, and sn=an+bn for every n⩾0, then ssn=sn+1+psn−1 for every n⩾1 hence one can compute recursively (sn)n⩾0 using

s0=2s1=ssn+1=ssn−psn−1 (n⩾1).

Alternatively, the vectors vn=(sn,sn−1) are such that vn+1=vnM, where M=(s−p10), hence vn=(s,2)Mn−1 for every n⩾1, that is, if Mk=(xkzkyktk), then sn=sxn−1+2zn−1 or sn=syn+2tn.

Share Follow

answered

Mar 5 '13 at 9:58

Did

263k●2626 gold badges●256256 silver badges●516516 bronze badges edited

Mar 5 '13 at 10:05

Up vote

8

Down vote

Consider the diagonal matrix M=(a00b).

You know its trace a+b and determinant ab, so you know its minimal polynomial M2−(a+b)M+ab.

You want to find tr(Mn). Since the trace is linear, the sequence (tn=tr(Mn)) satisfies the same recurrence linear relation as M : tn+2=(a+b).trn+1−ab.tn

Now, consider Xn=(tntn+1). You find that Xn+1=(0−ab1a+b)Xn. Since X0=(2a+b), you obtain Xn=(0−ab1a+b)n(2a+b).

Now, this is a matrix you actually know, so you can compute its nth power (use binary exponentiation to be fast), apply it to X0, and read the first coordinate to obtain tn