3

Let $a_n$ be given recursively by

$$a_n = \begin{cases} 30 & \text{if } n = 0\\\\ 144 & \text{if } n = 1\\\\ 698 & \text{if } n = 2\\\\ 12 a_{n−1} − 47 a_{n−2} + 60 a_{n−3} & \text{if } n \geq 3\\\end{cases}$$

Prove that $a_n= 3^{n}+ 4^{n+1}+ 5^{n+2}$. For which $n$ is $a_n$ divisible by $3$?

I honestly have no idea how to approach this. I started with brute force to obtain $a_3$ and $a_4$ as $3,408$ and $16,730$ but I do not see any pattern in the sequence. I think induction could be one approach. Right now, I'm learning about congruence classes so that might be another route but I don't know how I'd apply it.

Community
  • 1
Remy
  • 8,128
  • 1
    Show that the explicit formula satisfies the recurrence. – Sri-Amirthan Theivendran Oct 14 '17 at 21:26
  • 1
    There are at least 2 well established methods to solve such recurrences, generating functions and characteristic polynomials. – rtybase Oct 14 '17 at 21:36
  • Ever used matrices to find the $n$-th Fibonacci number? This is similar, but it uses $3 \times 3$ matrices instead of $2 \times 2$ matrices. – Rodrigo de Azevedo Oct 14 '17 at 21:36
  • I have not used matrices to find the $n$-th Fibinacci number. And I will look into those two methods. Which one would you recommend? – Remy Oct 14 '17 at 21:37
  • 1
    Characteristic polynomials are generally easier ... but generating functions are more general, here is an example https://math.stackexchange.com/questions/2461496/solving-x-n-3x-n-1-8-with-n-geq-1-and-x-0-2/2461626#2461626 – rtybase Oct 14 '17 at 21:40
  • 2
    Hint: $$(x-3)(x-4)(x-5)=x^3-12x^2+47x-60.$$ – Jyrki Lahtonen Oct 14 '17 at 21:41
  • 1
    Hint2: $4^k\equiv1^k$, $5^k\equiv(-1)^k$. – Jyrki Lahtonen Oct 14 '17 at 21:45
  • Could you explain your second hint? Don't you need to specify the modulo? Oh, is that for the second question? – Remy Oct 14 '17 at 21:54
  • Your title and question body are quite different. The title can be satisfied by direct computation. Just plug the expression into the recurrence. That doesn't prove that is the only expression that does, which is what the body asks for and depends on the given starting values. – Ross Millikan Oct 14 '17 at 22:39
  • Someone edited the title. But based on the body, I don't think it needs to be the only expression which satisfies it. I think I just need to show that the explicit formula for $a_n$ is satisfied. – Remy Oct 14 '17 at 22:42

2 Answers2

3

Hint: $x^3-12x^2+47x-60=(x-3)(x-4)(x-5)$

Let $Sa_n=a_{n+1}$ be the shift operator on sequences. Then. since $(S-a)\,a^n=0$, we have $$ (S-3)(S-4)(S-5)\left(A\cdot3^n+B\cdot4^n+C\cdot5^n\right)=0 $$

robjohn
  • 345,667
2

First part

From characteristic polynomials point of view, the recurrence $$a_n=12a_{n-1}-47a_{n-2}+60a_{n-3}$$ has the following characteristic polynomial (as it was pointed by Jyrki Lahtonen in the comments) $$x^3-12x^2+47x-60$$ which has the following roots $r_1=3, r_2=4,r_5=5$. Thus the general term of the recurrence is $$a_n=Ar_1^n+Br_2^n+Cr_3^n=A\cdot3^n+B\cdot4^n+C\cdot5^n$$ Given the initial values, we have the following system of linear equations $$\left\{\begin{matrix} 30=A+B+C \\ 144=A\cdot3+B\cdot4+C\cdot5 \\ 698=A\cdot3^2+B\cdot4^2+C\cdot5^2 \end{matrix}\right.$$ which yields the following solution $A=1, B=4, C=25$. As a result: $$a_n=3^n+4^{n+1}+5^{n+2}$$

Second part $$3 \mid a_n \Leftrightarrow 3 \mid 4^{n+1}+5^{n+2}$$ But $$4 \equiv 1 \pmod{3} \text{ then } 4^{n+1} \equiv 1 \pmod{3}$$ $$5 \equiv -1 \pmod{3} \text{ then } 5^{n+2} \equiv (-1)^{n+2} \pmod{3} $$ Thus $$3 \mid 4^{n+1}+5^{n+2} \Leftrightarrow 3 \mid 1 + (-1)^{n+2}$$ which says for odd $n$, $3 \mid a_n$, but it also works for $n=0$.

rtybase
  • 16,907