Question

I need help solving this proof. (It'll be in my next reply so I can do the formatting on it)

Answer 1

\[4|3^{2n-1} +1\] for integer >= 1

Answer 2

There are two ways you can prove this: (1) using congruences and modular arithmetic, or (2) mathematical induction. Are you familiar with either of these methods?

Answer 3

I am familiar with induction. I have used it to solve similar proofs but they are usually much less complex stuff like basic summation formulas.

Answer 4

And here is what I have so far.


3^(2k-1) + 1 = 4m
3^(2k+1-1) + 1 = 4m

Answer 5

The first thing you want to do is prove the base case \(n=1\). Can you do that?

Then you want to assume for some \(k>1\) that \(\large 4\mid 3^{2k-1}+1\implies 3^{2k-1}+1=4m\). Then your objective is to show that you can rewrite \(\large 3^{2(k+1)-1}+1 = 3^{2k+1}+1\) as a multiple of \(4\). So we note that
\[\large \begin{aligned}3^{2k+1}+1 &= 3^2\cdot 3^{2k-1}+1\\ & = 9\cdot 3^{2k-1}+1\\ &= (8+1)\cdot 3^{2k-1}+1\\ &= \ldots\end{aligned}\]
Can you see how to proceed from here? :-)

Answer 6

Yeah base case seems simple enough you eventually get 4|4.

Do you then take (8+1)? Leaving you with
4(2+1)?

Is that it? Is that the whole thing?

Answer 7

That should be one fourth and not 1.

Answer 8

Well I guess since 4 * anything makes that something divisible by 4 that proves that the right side is divisible by 4. But why did we start with the original equation and not the k+1?

Answer 9

Though I suppose you could do...
(8+1)*(3^2k)
4(2+1/4)*(3^2k) = 4m

Is that right?

Answer 10

And the m on the right side would be.....(2+1/4)*(3^2k)...

Answer 11

Though that can't be right because 2 + 1/4 is not an integer so it's not an integer by closure.

So yeah I don't know what to do.

Answer 12

continuing where I left off, we see that
\[\large \begin{aligned}(8+1)\cdot 3^{2k-1}+1 &= 8\cdot 3^{2k-1} + \underbrace{3^{2k-1}+1}_{=4m\text{ by ind. hypothesis}}\\ &= 8\cdot 3^{2k-1} + 4m\\ &= 4\underbrace{(2\cdot 3^{2-1}+m)}_{\in\Bbb{z};\text{ call it $a$}}\\ &= 4a\end{aligned}\]
Thus, \(\large 4\mid 3^{2k+1}+1\) and the inductive step is complete. Therefore \(\large 4\mid 3^{2n-1}+1\).

Does this make sense? :-)

Answer 13

The last under brace is supposed to read "\(\in\Bbb{Z}; \text{ call it $a$}\)"

Answer 14

How did you go from 8+1 to 8 *?
I am assuming you multiplied 1 with what was on the right side and then added it?

Answer 15

Well \(\large (8+1)\cdot 3^{2k-1} = 8\cdot 3^{2k-1} + 3^{2k-1}\) by the distributive property.

Answer 16

And then you set 3^2k-1 + 1 to 4m?
Can you explain why you are able to do that?

Answer 17

I noticed that I had two typos in that equation block; here's the corrected form.

\[\large \begin{aligned}(8+1)\cdot 3^{2k-1}+1 &= 8\cdot 3^{2k-1} + \underbrace{3^{2k-1}+1}_{=4m\text{ by ind. hypothesis}}\\ &= 8\cdot 3^{2k-1} + 4m\\ &= 4\underbrace{(2\cdot 3^{2k-1}+m)}_{\in\Bbb{Z};\text{ call it $a$}}\\ &= 4a\end{aligned}\]

Answer 18

We made the assumption that for some \(\large k\), we have \(\large \color{red}{3^{2k-1}+1=4m}\); this is known as the inductive hypothesis. Whenever you try to show the statement is true for \(\large k+1\), you need to use the inductive hypothesis at some point. So when you rewrite
\[\large 9\cdot 3^{2k-1}+1 = (8+1)\cdot 3^{2k-1}+1 = 8\cdot 3^{2k-1}+\color{red}{3^{2k-1}+1} \]
we see the term that appears in our inductive hypothesis pop up, so that's where you make the substitution.

Does this clarify things?

Answer 19

Okay I understand why you are able to place that into 4m.

Why did we assume 3^2k-1 = 4m
and not
3^2k+1-1 = 4m

Answer 20

I forgot a plus 1 in that last equation.

Answer 21

First note that \(\large\displaystyle 4\mid 3^{2n-1}+1 \implies 3^{2n-1}+1=4m\). So then, if you let \(\large n=k\), you have \(\large 3^{2k-1}+1=4m\) and the objective of the induction is to show that \(\large 3^{2(k+1)-1}+1=4a\). If you want to start with \(\large 3^{2k+1}+1=4m\), then the objective of induction is to show that \(\large 3^{2(k+2)-1}+1 =4a \implies 3^{2k+3}+1=4a\).

In general, when you prove something with mathematical induction, we assume that it's true for k, and then show it's true for k+1. You could alternately assume it's true for k+1, but then you'd have to show it's true for k+2.

Does this make sense?

Answer 22

Ah I gotcha. I had just seen other problems done by doing some stuff with whatever your term was plus 1.