1. ## Induction Help

So I came across this induction question and am quite stuck mid-way.
The question is: Prove that $2^n + 1$ is divisible by $3$ for all odd integers $n$

So far, I have this working out done:

1. To prove: $2^n - 1 = 3M$, where $M \in \mathbb{Z}$
Prove true for $n=1$
$LHS = 2^1 + 1$
$= 3$ which is divisible by 3
So the statement is true for $n=1$

2. Assume true for $n=2k -1$, where $k \in \mathbb{Z}$
i.e. $2^{2k-1} + 1 = 3N$, where $N \in \mathbb{Z}$

3. Prove true for $n=k+1$
To prove: $2^{k+1} + 1 = 3P$, where $P \in \mathbb{Z}$
$LHS = 2^{k+1} + 1$

Aaaand I'm stuck at that step. I've no idea how to manipulate the LHS so that the assumption from 2 can be subbed into 3. Also, is the working so far correct? Thanks!

2. ## Re: Induction Help

Originally Posted by alussovsky
So I came across this induction question and am quite stuck mid-way.
The question is: Prove that $2^n + 1$ is divisible by $3$ for all odd integers $n$

So far, I have this working out done:

1. To prove: $2^n - 1 = 3M$, where $M \in \mathbb{Z}$
Prove true for $n=1$
$LHS = 2^1 + 1$
$= 3$ which is divisible by 3
So the statement is true for $n=1$

2. Assume true for $n=2k -1$, where $k \in \mathbb{Z}$
i.e. $2^{2k-1} + 1 = 3N$, where $N \in \mathbb{Z}$

3. Prove true for $n=k+1$
To prove: $2^{k+1} + 1 = 3P$, where $P \in \mathbb{Z}$
$LHS = 2^{k+1} + 1$

Aaaand I'm stuck at that step. I've no idea how to manipulate the LHS so that the assumption from 2 can be subbed into 3. Also, is the working so far correct? Thanks!
$\noindent For your step 3, you should show the statement is true for n = 2k+1, i.e. the \textbf{next odd number} from your inductive hypothesis.$

3. ## Re: Induction Help

Also, thanks for posting your attempts!

4. ## Re: Induction Help

Originally Posted by alussovsky
So I came across this induction question and am quite stuck mid-way.
The question is: Prove that $2^n + 1$ is divisible by $3$ for all odd integers $n$

So far, I have this working out done:

1. To prove: $2^n - 1 = 3M$, where $M \in \mathbb{Z}$
Prove true for $n=1$
$LHS = 2^1 + 1$
$= 3$ which is divisible by 3
So the statement is true for $n=1$

2. Assume true for $n=2k -1$, where $k \in \mathbb{Z}$
i.e. $2^{2k-1} + 1 = 3N$, where $N \in \mathbb{Z}$

3. Prove true for $n=k+1$
To prove: $2^{k+1} + 1 = 3P$, where $P \in \mathbb{Z}$
$LHS = 2^{k+1} + 1$

Aaaand I'm stuck at that step. I've no idea how to manipulate the LHS so that the assumption from 2 can be subbed into 3. Also, is the working so far correct? Thanks!
some critisicm: when you say $\mathbb{Z}$ always say $\mathbb{Z^{+}}$ or $\mathbb{N}$ since by only $\mathbb{Z}$ you can include the negative set which is Wrong. Since Induction USUALLY deals with $n \geq 1$

Anyway, for step 2, the assumption satge I would say $2k+1$ and for the proving step, I would let $n=2k+3$ ; it makes it easier this way!

5. ## Re: Induction Help

Originally Posted by InteGrand
$\noindent For your step 3, you should show the statement is true for n = 2k+1, i.e. the \textbf{next odd number} from your inductive hypothesis.$
Thank you for the help! ... but I'm still a bit stuck on step 3, sorry ^^" How would you manipulate $2^{2k+1} + 1 = 3P$ so that you can substitute the $2^{2k-1} + 1 = 3N$ from the step 2 assumption?

6. ## Re: Induction Help

Thank you for pointing that out! Even in written down working out, I keep forgetting that plus sign, so I'll make sure to check that it's in next time, haha.

In class, my teacher said that when proving for odd integers, you should always use the assumption $2k - 1$ so that the odd integer 1 is not excluded! Is that true or is still alright to use $2k +1$?

7. ## Re: Induction Help

Originally Posted by alussovsky
Thank you for the help! ... but I'm still a bit stuck on step 3, sorry ^^" How would you manipulate $2^{2k+1} + 1 = 3P$ so that you can substitute the $2^{2k-1} + 1 = 3N$ from the step 2 assumption?
$\noindent You're welcome! And here's a hint: try and write 2^{2k+1} in terms of 2^{2k-1}.$

8. ## Re: Induction Help

Originally Posted by InteGrand
$\noindent You're welcome! And here's a hint: try and write 2^{2k+1} in terms of 2^{2k-1}.$
I... think I get it?! Maybe?! Just to check,

$LHS = 2^{2k+1} + 1$
$= 2^{2k} \times 2 + 1$
$= \frac{2^{2k}}{2} \times 4 + 1$
$= 2^{2k-1} \times 4 + 1$
$= 2^{2k-1} \times 3 + 2^{2k-1} + 1$
$= 3(2^{2k-1}) + 3N$ from previous assumption
$= 3(2^{2k-1} + N)$
$= 3P$ as since $N, k \in \mathbb{Z^+},$ then $2^{2k-1} + N \in \mathbb{Z^+}$

... which I hope is correct. Thank you for all of your help though!

9. ## Re: Induction Help

Originally Posted by alussovsky
I... think I get it?! Maybe?! Just to check,

$LHS = 2^{2k+1} + 1$
$= 2^{2k} \times 2 + 1$
$= \frac{2^{2k}}{2} \times 4 + 1$
$= 2^{2k-1} \times 4 + 1$
$= 2^{2k-1} \times 3 + 2^{2k-1} + 1$
$= 3(2^{2k-1}) + 3N$ from previous assumption
$= 3(2^{2k-1} + N)$
$= 3P$ as since $N, k \in \mathbb{Z^+},$ then $2^{2k-1} + N \in \mathbb{Z^+}$

... which I hope is correct. Thank you for all of your help though!
Well done! And no worries.

10. ## Re: Induction Help

Originally Posted by InteGrand
Well done! And no worries.
Once again (you're probably sick of hearing this by this point XD) thank you so much for all your help!

11. ## Re: Induction Help

Originally Posted by alussovsky
Thank you for pointing that out! Even in written down working out, I keep forgetting that plus sign, so I'll make sure to check that it's in next time, haha.

In class, my teacher said that when proving for odd integers, you should always use the assumption $2k - 1$ so that the odd integer 1 is not excluded! Is that true or is still alright to use $2k +1$?
$\noindent You can use either one, just remember that \boxed{n\geq 1} in the inductive hypothesis. So if you say that \color{blue}n = 2k-1, then you should say that \color{blue}k\geq 1. If instead you say that \color{red}n = 2k+1 in the inductive hypothesis, then you should say that \color{red}k \geq 0.$

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•