Combinatoric sequence, please help me

**Ununuquantium** · September 1st 2007, 07:45 AM

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

**ThePerfectHacker** · September 1st 2007, 05:20 PM

Originally Posted by Ununuquantium

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

You can find the general expression for $a_n$ .

Define the generating function,
$f(x) = a_1+a_2x+a_3x^2+...$
Now consider,
$x^2f(x) - 3xf(x) -5x^2f(x) = 0$
And find the form of $a_n$ ...

**Ununuquantium** · September 2nd 2007, 12:13 AM

General expression doesn't work

**Opalg** · September 2nd 2007, 12:45 AM

Originally Posted by Ununuquantium

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

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

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

That contradiction shows more than was asked for, namely that none of the prime divisors of $a_{n}$ can divide $a_{n+1}$ or $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 $a_{n}=3a_{n - 1}+5a_{n - 2}$ says that if $a_n$ is a multiple of 3 then so is $a_{n-2}$ . The "reverse induction" procedure then tells us that either $a_2$ or $a_1$ is a multiple of 3, which is a contradiction.

In the same way, if p = 5 and $a_n$ is a multiple of 5 then the recurrence relation shows that $a_{n-1}$ is a multiple of 5. Continuing down the sequence to $a_1$ , we again get a contradiction.

**Ununuquantium** · September 5th 2007, 08:05 AM

Yes:
I made it also by induction, it is similar:
First I prove that every number from the sequence is not divisible by $5$ :

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

I do similar with division by $3$ .

And then, also proving by induction I say:

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

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

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

Thread: Combinatoric sequence, please help me

LinkBack

Thread Tools

Display

Combinatoric sequence, please help me

Similar Math Help Forum Discussions

Even vs. Odd in a combinatoric proof

Two combinatoric problems

Need help with Combinatoric Proof

combinatoric thing

combinatoric identity

Search Tags