$2 \cdot 4^{2n + 1} + 3^{3n + 1}$ is divisible by $\lambda$, for all $n \in N$. Find $\lambda$.

Question

I'll state the question here:

If "$P(n): 2 \cdot 4^{2n + 1} + 3^{3n + 1}$ is divisible by $\lambda$, for all $n \in N$" is true, then what is the value of $\lambda$?

This is what I can think of:

$P(1): 2 \cdot 4^{2(1) + 1} + 3^{3(1) + 1}$ is divisible by $\lambda$.

i.e., $209$ is divisible by $\lambda$.

And,

$P(2): 2 \cdot 4^{2(2) + 1} + 3^{3(2) + 1}$ is divisible by $\lambda$.

i.e., $4235$ is divisible by $\lambda$.

Now the common factors of the $209$ and $4235$ are $1$ and $11$. So, $\lambda$ is one of $1$ and $11$. My textbook says that the answer is 11. And this how it was solved in the book.

Now I can't understand why can't the answer be $1$? Is doing what I did above enough to state the answer as $11$? What if for some $k \in N$, $2 \cdot 4^{2n + 1} + 3^{3n + 1}$ is not divisible by $11$? So to avoid missing such a term, I believe I should substitute $\lambda$ with $11$ in the statement and prove the statement using induction (that is what the chapter in my book is about). If I am able to prove it (and I will be since it's true), the answer is $11$. Otherwise, the answer is $1$.

My doubt is regarding the approach to the question. Does the method by which I solved it above suffice to give the answer as $11$? Or, as I mentioned in the previous paragraph, do I have to prove the statement again by replacing $\lambda$ with $11$?

Answer 1

Hint $\ {\rm mod}\ 11\!:\,\ 8\cdot 16^n + 3\cdot \overbrace{ \color{#c00}{27}^n}^{\textstyle\color{#c00}{16}^n}\equiv 11\cdot 16^n\equiv 0\ $ by $\ \color{#c00}{27\equiv 16}\,$ & Congruence Power Rule.

Remark $ $ If modular arithmetic is unfamiliar then we can instead rewrite is as follows

$$ 3(27^n\!-16^n) + 11\cdot 16^n$$

which is divisible by $11$ by $\,11 = 27\!-\!16\mid 27^n\!-16^n$ (provable by induction or by invoking the Factor Theorem $\, a-b\mid a^n-b^n)$

Induction is also (implicitly) used in the modular proof because it uses $\,27\equiv 16\,\Rightarrow\, 27^n\equiv 16^n\,$ and the proof of this Congruence Power Rule is by induction on $\,n$.

Update $ $ OP seeks a direct inductive proof without modular arithmetic etc. Below is one.

$$\begin{align} f(n)\ &=\qquad 8\cdot 16^n +\, 3\cdot 27^n\\ \Rightarrow\ f(n\!+\!1)\ &=\, 8\cdot \color{#0a0}{16}\cdot 16^n +\, 3(\color{#0a0}{16}\!+\!11)\, 27^n\\ &=\, \color{#0a0}{16}\ \color{#c00}{f(n)}\ \ \ +\ \ \ 3\cdot \color{}{11}\cdot 27^n\\ &=\, \color{#c00}{11} (\color{#0a0}{16}\, \color{#c00}m\ \ +\,\ \ 3\cdot 27^n)\ \ {\rm by}\,\ \color{#c00}{f(n) = 11m}\,\ {\rm(inductive\ hypothesis)} \end{align}$$

therefore $\ f(n) = 11m\,\Rightarrow\, f(n\!+\!1) = \color{#c00}{11}k,\ $ i.e. $\,11\mid f(n)\,\Rightarrow\, 11\mid f(n\!+\!1)$.

Answer 2

You've proved $\lambda$ divides $11$. To see that $11$ divides $\lambda$, we need to show that $11$ divides $f(n)$ for all $n$. To see this let's use induction on $n$, and note that $f(n) = g(n) + h(n)$ where: $$g(0) = 8\\ h(0) = 3\\ g(n+1) = 16g(n) = 11g(n)+ 5g(n)\\ h(n+1) = 27h(n) = 11\cdot 2h(n) + 5h(n) $$ So $11$ certainly divides $f(0) = 11$ and we have $$ f(n+1) = 11(g(n) + 2h(n)) + 5(g(n) + h(n)) = 11(g(n)+2h(n)) + 5f(n). $$

Hence, if $11$ divides $f(n)$, it will also divide $f(n+1)$. So $11$ divides $f(n)$ for all $n$ by induction.

Answer 3

Take it modulo 11:

$2\cdot4^{2n + 1} + 3^{3n + 1} = 8 \cdot 5^n + 3 \cdot 5^n = 11 \cdot 5^n = 0$

Answer 4

Note that any numbers of the form $u_n=Aa^n+Bb^n$ satisfy the recurrence $u_{n+1}=(a+b)u_n-abu_{n-1}$ (easy to check directly). You can use this to show that any number which is a factor of $u_1$ and $u_2$ is a factor of $u_n$ for $n\ge 1$.

Here you use $a=16, b=27$

---

This works as follows. $a,b$ are the roots of the equation $(x-a)(x-b)=0$ so that $x^2=(a+b)x-ab$. Multiply through by $x^{n-1}$ and this gives $x^{n+1}=(a+b)x^n-(ab)x^{n-1}$. This still has roots $a$ and $b$ so setting $x=a$ and multiplying through by $A$ gives $$Aa^{n+1}=A(a+b)a^n-A(ab)a^{n-1}$$ Similarly with $b, B$$$Bb^{n+1}=B(a+b)b^n-B(ab)b^{n-1}$$

Adding these together gives $$Aa^{n+1}+Bb^{n+1}=(a+b)(Aa^n+Bb^n)-(ab)(Aa^{n-1}+Bb^{n-1})$$ which is just $$u_{n+1}=(a+b)u_n-abu_{n-1}$$