We have a integer sequence: , , , .... and we have

.

Does exist integer number such that is a divisor of ??

Printable View

- Sep 1st 2007, 07:45 AMUnunuquantiumCombinatoric sequence, please help me
We have a integer sequence: , , , .... and we have

.

Does exist integer number such that is a divisor of ?? - Sep 1st 2007, 05:20 PMThePerfectHacker
- Sep 2nd 2007, 12:13 AMUnunuquantium
General expression doesn't work

- Sep 2nd 2007, 12:45 AMOpalg
Suppose (in order to get a contradiction) that divides .

Let*p*be a prime divisor of . Then*p*must divide one or other of and . But this means that*p*divides two of the three terms in the relation and therefore it divides the third one as well. However, , and since*p*divides and it must also divide . Continuing in this way by "reverse induction", you see that*p*must divide , , ..., and eventually that*p*divides .

That contradiction shows more than was asked for, namely that none of the prime divisors of can divide or .

**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 says that if is a multiple of 3 then so is . The "reverse induction" procedure then tells us that either or is a multiple of 3, which is a contradiction.

In the same way, if*p*= 5 and is a multiple of 5 then the recurrence relation shows that is a multiple of 5. Continuing down the sequence to , we again get a contradiction. - Sep 5th 2007, 08:05 AMUnunuquantium
Yes:

I made it also by induction, it is similar:

First I prove that every number from the sequence is not divisible by :

**I****NDUCTION BASE**: I see that doesn't divide , where .

**Induction step**: I will prove for arbitrary (integer)

that if is not divisible by therefore is also not divisible by .

I do similar with division by .

And then, also proving by induction I say:

Every three consecutive numbers in the sequence ( ) are relatively prime [we also know now that every number from the sequence is not divisible by and ]:.

**INDUCTION BASE**: Let - so are relatively prime.

**Induction step**: I will prove that if therefore . So, we see that are reletively prime - so is also relatively prime with - it is easy to deduce.

Taht's why there does not exist such (integer of course) that is divisor of

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