0
$\begingroup$

Let $a_1 = 3, a_2 = 18$, and $a_n = 6a_{n-1} − 9a_{n-2}$ for each integer $n \ge 3$. Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$

I've done the base step and ih however I am stuck on the Inductive Step. I'm thinking it's something like $a_{k+1} = 6a_k - 9a_{k-1}$ but I don't know how to follow that.

Thanks in advance for the help with the Inductive Step.

$\endgroup$
  • $\begingroup$ $3$ and $18$ are both divisible by $3$, yes? Therefore $a_3$ is divisible by $3$...and the $a_2$ and $a_3$, then therefore $a_3$ and $a_4$, etc. Assume that $a_{n - ?}$ is divisible by $3$ and therefore $a_n$ is also divisible by $3$. $\endgroup$ – Jared Apr 10 '16 at 6:02
2
$\begingroup$

Let $3^{n-2}|a_{n-2}$ and $3^{n-1}|a_{n-1}$. Then $a_{n-2}=3^{n-2}A, a_{n-1}=3^{n-1}B, A,B \in \mathbb Z$ $$a_n=6a_{n-1}-9a_{n-2}=6\cdot 3^{n-1}B-9\cdot 3^{n-2}A=3^n(2B-A)$$

$\endgroup$
1
$\begingroup$

Initial: $a_1,a_2$ are divisible by $3^1,3^2$, respectively.

Inductive hypothesis: $a_{n-1}$ is divisible by $3^{n-1}$, and this pattern holds for all indices less than $n$.

Inductive step: We wish to show that there exists a integer $m$ such that $a_n = m 3^n$. Observe that there exists $u,v$ such that $a_{n-1} = 3^{n-1} u, a_{n-2} = 3^{n-2} v$. Hence $$ a_n = 6a_{n-1} - 9a_{n-2} = 6\cdot 3^{n-1} u - 9 \cdot 3^{n-2} v = 2 \cdot 3^n u - 3^n v = 3^n (2u - v) $$ so we can let $m = 2u - v$.

$\endgroup$
0
$\begingroup$

Use strong induction: assume $a_{n - 2} = 3^{n - 2}\lambda_{n - 2}$ and $a_{n - 1} = 3^{n - 1}\lambda_{n - 1}$. We then have:

\begin{align} a_n =&\ 2\cdot 3\cdot 3^{n - 1}\lambda_{n - 1} - 3^2\cdot 3^{n - 2}\lambda_{n - 2}\\ =&\ 2\lambda_{n - 1}3^n - \lambda_{n - 2}3^n \\ =&\ \left(2\lambda_{n - 1} - \lambda_{n - 2}\right)3^n \end{align}

$2\lambda_{n - 1} - \lambda_{n - 2}$ is surely an integer (integers are closed under addition and multiplication) therefore $a_n$ is a multiple of $3^n$. The only thing left is to show that $a_1$ and $a_2$ satisfy this condition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.