prove by induction: $\forall n \in N, \exists k \in N: 165^{2n} - 1 = 166k$

Question

I am trying to prove by induction: $\forall n \in N, \exists k \in N: 165^{2n} - 1 = 166k$.

But I've never come across having to possibly induct on two variables?

The base case for $n=1$ is true for $k = 164$

With the inductive hypothesis: assume $165^{k} - 1 = 166k$ we will prove that $165^{2k+2} - 1 = 166k$.

Where can I start on the inductive step?

Answer 1

For $n=m\in\Bbb N$ let $165^{2m}-1 = 166 k \implies \color{blue}{165^{2m} = 166k+1}\ , k \in \Bbb N$
For $n=m+1$,

$$165^{2m+2} - 1 = \color{blue}{165^{2m}}\cdot165^2-1 = (\color{blue}{166k+1})165^2 - 1$$ $$165^{2m+2} - 1 = 166\cdot165^2k+165^2-1 = 166\cdot165^2k+166\cdot164 = 166k'$$

$k' = 165^2k+164\in \Bbb N$

Answer 2

Hint : For induction, the base case is fine, and suppose that $165^{2n}- 1 = 166 k_n$ for some integer $k_n$ depending on $n$.

Then note that $$(165^{2(n+1)}-1) - (165^{2n}-1) = 165^{2(n+2)} - 165^{2n} = 165^{2n}(165^2-1) = 165^{2n} \times 166 \times 164$$

And find $k_{n+1}$ in terms of $k_n$ now.

Answer 3

If $f(m)=165^{2m}-1,$

$f(n+1)-165^2f(n)=-1+165^2=(165+1)(165-1)$

As $(165^2,165^2-1)=1,$

$(165^2-1)$ will divide $f(n+1)$

$\iff(165^2-1)$ divides $f(n)$

Now establish the base case

Answer 4

If you are going to use $k$ as your induction variable you will have to use a different variable your statement. Assume $165^{2k} - 1= 166m$ and for $2k+2$ the number will change so you'll need a third variable for that.

I suggest that you use subscripts for your $m$ variable.

We will assume $166^{2k} - 1 = 166m_k$ and we need to prove that $165^{2k+2}-1 =166m_{k+1}$ for some integer $m_{k+1}$.

Basic step: $n=1$ then we want to prove $165^n - 1= 166m_1$ for some $m_1$.

That $165^2 -1 = (165 + 1)(165-1) = 166*164$ so if we let $m_1 = 164$ that is the base case.

Induction step.

Assume $165^{2k} -1 = 166m_k$ for some $m_k$ we want to prove that $165^{2k+2} -1 = 166*m_{k+1}$ for some integer $m_{k+1}$.

Start by noting:

$165^{2k+2}-1=165^{2k}165^2 - 1=$

$165^{2k}*165^2 - 165^2 + 165^2 - 1 =$

$165^2(165^{2k} -1) + (165^2 - 1) = $

$165^2(166m_k) + (166m_1) = $

$166[ 165^2m_k + m_1]$

So if we let $m_{k+1} = 165^2m_k + m_1$ were are done.