1
$\begingroup$

Let $A_1=0$ and $A_2=1$ and suppose that the number $A_n$ is obtained from the decimal expansions of $A_{n-1}$ and $A_{n-2}$. For example $A_3=A_2A_1=10$; $A_4=A_3A_2=101$; $A_5=A_4A_3=10110$.

Determine the integers $n$ that satisfy the condition $A_n \equiv 0 \pmod{11}$.


Progress

If I want a number congruent with 0 then I want multiples of 11. The problem is how to find the $n$'s that satisfy the terms. I could use the fact that a number is divisible by 11 when the sum of even order of digits $S_p$ less the sum of odd order digits $S_i$ are a number divisible by 11. But how?

$\endgroup$
  • $\begingroup$ This might help: math.stackexchange.com/questions/916408/… $\endgroup$ – Johanna Jan 3 '15 at 17:52
  • $\begingroup$ A number is always congruent with -1 or 1 (mod 11). So if I want on that is congruent with 0 than I want multiples of 11. The problem is how to find the "n"'s that satisfy the terms. I could use the fact that a number is divisible by 11 when the sum of even order of digits Sp less the sum of Si odd order numbers are a number divisible by 11? $\endgroup$ – Matt Jan 3 '15 at 17:59
  • 1
    $\begingroup$ Rabbit Sequence: maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrab.html $\endgroup$ – Aryabhata Jan 3 '15 at 19:46
1
$\begingroup$

The key is to recognize that each $A_n$ has $F_n$ digits, so that

$$A_n=10^{F_{n-2}}A_{n-1}+A_{n-2}$$

for $n\ge 3$. Thus,

$$A_n\equiv 10^{F_{n-2}}A_{n-1}+A_{n-2}\equiv(-1)^{F_{n-2}}A_{n-1}+A_{n-2}\pmod{11}\;.$$

It’s easy to show by induction that $F_n$ is even if and only if $n$ is a multiple of $3$, so

$$A_n\equiv\begin{cases} A_{n-2}+A_{n-1}\pmod{11},&\text{if }n\equiv2\pmod3\\ A_{n-2}-A_{n-1}\pmod{11},&\text{otherwise}\;. \end{cases}$$

Let $B_1=A_1=0$ $B_2=A_2=1$, and

$$B_n=\begin{cases} B_{n-2}+B_{n-1},&\text{if }n\equiv2\pmod3\\ B_{n-2}-B_{n-1},&\text{otherwise}\;; \end{cases}$$

clearly $B_n\equiv A_n\pmod{11}$ for $n\in\Bbb Z^+$. Now calculate a few values of $B_n$

$$\begin{array}{rcc} n:&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\ B_n:&0&1&-1&2&1&1&0&1&-1&2&1&1&0&1 \end{array}$$

At this point it’s pretty obvious that $\langle B_n:n\in\Bbb Z^+\rangle$ is periodic with period $6$, and it’s not at all difficult to prove this by induction. It follows that $A_n$ is divisible by $11$ precisely when $n\equiv 1\pmod 6$.

By the way, it’s also not hard to show by induction on $n$ that $B_n$ is the sum of the digits of $A_n$ corresponding to even powers of $10$ minus the sum of the digits of $A_n$ corresponding to odd powers of $10$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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