• Sep 1st 2007, 07:45 AM
Ununuquantium
We have a integer sequence: \$\displaystyle a_{1}\$, \$\displaystyle a_{2}\$, \$\displaystyle a_{3}\$, .... and we have
\$\displaystyle a_{1}=1\$
\$\displaystyle a_{2}=2\$.
\$\displaystyle a_{n}=3a_{n - 1}+5a_{n - 2}\$
\$\displaystyle n=3,4,5....\$
Does exist integer number \$\displaystyle x\geqslant 2\$ such that \$\displaystyle a_{x}\$ is a divisor of \$\displaystyle a_{x + 1}a_{x + 2}\$ ??
• Sep 1st 2007, 05:20 PM
ThePerfectHacker
Quote:

Originally Posted by Ununuquantium
We have a integer sequence: \$\displaystyle a_{1}\$, \$\displaystyle a_{2}\$, \$\displaystyle a_{3}\$, .... and we have
\$\displaystyle a_{1}=1\$
\$\displaystyle a_{2}=2\$.
\$\displaystyle a_{n}=3a_{n - 1}+5a_{n - 2}\$
\$\displaystyle n=3,4,5....\$
Does exist integer number \$\displaystyle x\geqslant 2\$ such that \$\displaystyle a_{x}\$ is a divisor of \$\displaystyle a_{x + 1}a_{x + 2}\$ ??

You can find the general expression for \$\displaystyle a_n\$.

Define the generating function,
\$\displaystyle f(x) = a_1+a_2x+a_3x^2+...\$
Now consider,
\$\displaystyle x^2f(x) - 3xf(x) -5x^2f(x) = 0\$
And find the form of \$\displaystyle a_n\$ ...
• Sep 2nd 2007, 12:13 AM
Ununuquantium
General expression doesn't work
• Sep 2nd 2007, 12:45 AM
Opalg
Quote:

Originally Posted by Ununuquantium
We have a integer sequence: \$\displaystyle a_{1}\$, \$\displaystyle a_{2}\$, \$\displaystyle a_{3}\$, .... and we have
\$\displaystyle a_{1}=1\$
\$\displaystyle a_{2}=2\$.
\$\displaystyle a_{n}=3a_{n - 1}+5a_{n - 2}\$
\$\displaystyle n=3,4,5....\$
Does exist integer number \$\displaystyle x\geqslant 2\$ such that \$\displaystyle a_{x}\$ is a divisor of \$\displaystyle a_{x + 1}a_{x + 2}\$ ??

Suppose (in order to get a contradiction) that \$\displaystyle a_n\$ divides \$\displaystyle a_{n + 1}a_{n + 2}\$.

Let p be a prime divisor of \$\displaystyle a_n\$. Then p must divide one or other of \$\displaystyle a_{n + 1}\$ and \$\displaystyle a_{n + 2}\$. But this means that p divides two of the three terms in the relation \$\displaystyle a_{n+2}=3a_{n + 1}+5a_{n}\$ and therefore it divides the third one as well. However, \$\displaystyle a_{n+1}=3a_{n}+5a_{n - 1}\$, and since p divides \$\displaystyle a_{n + 1}\$ and \$\displaystyle a_{n}\$ it must also divide \$\displaystyle a_{n-1}\$. Continuing in this way by "reverse induction", you see that p must divide \$\displaystyle a_{n-2}\$, \$\displaystyle a_{n-3}\$, ..., and eventually that p divides \$\displaystyle a_{1}=1\$.

That contradiction shows more than was asked for, namely that none of the prime divisors of \$\displaystyle a_{n}\$ can divide \$\displaystyle a_{n+1}\$ or \$\displaystyle a_{n+2}\$.

Edit: That proof doesn't quite work. It's okay unless p = 3 or 5. But those two primes will require some other argument. I don't have time to think about that just now.

Second edit: No real problem with p = 3 or 5. Suppose that p = 3. The recurrence relation \$\displaystyle a_{n}=3a_{n - 1}+5a_{n - 2}\$ says that if \$\displaystyle a_n\$ is a multiple of 3 then so is \$\displaystyle a_{n-2}\$. The "reverse induction" procedure then tells us that either \$\displaystyle a_2\$ or \$\displaystyle a_1\$ is a multiple of 3, which is a contradiction.

In the same way, if p = 5 and \$\displaystyle a_n\$ is a multiple of 5 then the recurrence relation shows that \$\displaystyle a_{n-1}\$ is a multiple of 5. Continuing down the sequence to \$\displaystyle a_1\$, we again get a contradiction.
• Sep 5th 2007, 08:05 AM
Ununuquantium
Yes:
I made it also by induction, it is similar:
First I prove that every number from the sequence is not divisible by \$\displaystyle 5\$:

INDUCTION BASE: I see that \$\displaystyle 5\$ doesn't divide \$\displaystyle a_{k}\$, where \$\displaystyle k=3\$.
Induction step: I will prove for arbitrary \$\displaystyle k\geqslant 3\$(integer)
that if \$\displaystyle a_{k}\$ is not divisible by \$\displaystyle 5\$ therefore \$\displaystyle a_{k+1}\$ is also not divisible by \$\displaystyle 5\$.

I do similar with division by \$\displaystyle 3\$.

And then, also proving by induction I say:

Every three consecutive numbers in the sequence \$\displaystyle a_{k}=3a_{k - 1}+5a_{k - 2}\$ (\$\displaystyle k\geqslant \$) are relatively prime [we also know now that every number from the sequence is not divisible by \$\displaystyle 5\$ and \$\displaystyle 3\$]:.
INDUCTION BASE: Let \$\displaystyle k=3\$ - so \$\displaystyle a_{1}, a_{2}, a_{3}\$ are relatively prime.
Induction step: I will prove that if \$\displaystyle a_{k}=3a_{k - 1}+5a_{k - 2}\$ therefore \$\displaystyle a_{k+1}=3a_{k}+5a_{k - 1}\$. So, we see that \$\displaystyle a_{k}, a_{k - 1}\$ are reletively prime - so \$\displaystyle a_{k+1}\$ is also relatively prime with \$\displaystyle a_{k}, a_{k - 1}\$ - it is easy to deduce.

Taht's why there does not exist such \$\displaystyle x\geqslant 2\$ (integer of course) that \$\displaystyle a_{x}\$ is divisor of \$\displaystyle a_{x + 1}a_{x + 2}\$

Can anybody check my proof, please - I am not a specialist