# Recursive sequence

1. Sep 15, 2007

### HallsofIvy

Staff Emeritus
1. The problem statement, all variables and given/known data
Sequence of integers a1, a2, a3, . . . is fixed by:
a1 =1,
a2 =2,
$$a_{n}={3a}_{n-1}+5a_{n-2}$$ for n=3,4,5, . . . .
Decide if exisist such an integer k$$\geq$$2, that $${a}_{k+1}\bullet {a}_{k+1}$$ is divisible by $${a}_{k}.$$

2. Relevant equations

Last edited: Sep 15, 2007
2. Sep 15, 2007

### HallsofIvy

Staff Emeritus
I edited to try to correct the Latex and accidently deleted the entire thread. Sorry about that. I don't know why the
$$a_n= 3a_{n-1}+ 5a_{n-2}$$
still won't come out properly.
To make up for that, I'll try to help with the question!

Before you can prove anything, you need to decide if it is true or false! The question asks b if there exist an integer larger than 1 such that $a_{k+1}^2$ is divisible by a_k.

From the recursion formula, $a_{k+1}= 3a_k+ 5a_{k-1}$.
$(a_{k+1})^2= 9a_k^2+ 30a_ka_{k-1}+ 25a_{k-1}$
Since the first two terms are obviously divisble by $a_k$, the whole thing is if and only if $25a_{k-1}^2$ is divisible by a_k.

That's as far as I can get. Don't know if it helps.

3. Sep 15, 2007

### Feldoh

Find a summation then use induction^^

4. Sep 18, 2007

### dalle

Notice that if $$a_{k+1}^2$$ is divisible by $$a_k$$ then there is a prime $$p$$ such that both $$a_{k+1}$$ and $$a_k$$ are divisible by $$p$$. in other words
$$a_{k+1} = 0$$ modulo $$p$$
$$a_k = 0$$ modulo $$p$$.

for a fixed prime $$q$$ define the sequence of integers $$b_1,b_2, \dots$$ by:
$$b_{1} = 1$$

$$b_{2} = 2$$

$$b_{n} = 3 b_{n-1} + 5 b_{n-2}$$ modulo $$q$$

Show: there is no integer k>=2 such that both $$b_k$$ and $$b_{k+1}$$ are 0.