Induction Help (1 Viewer)

alussovsky · Jan 28, 2019

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!

InteGrand · Jan 28, 2019

alussovsky said:
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.$

InteGrand · Jan 28, 2019

Also, thanks for posting your attempts!

HeroWise · Jan 29, 2019

alussovsky said:
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!

alussovsky · Jan 29, 2019

InteGrand said:
$\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?

alussovsky · Jan 29, 2019

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$ ?

InteGrand · Jan 29, 2019

alussovsky said:
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}$.$

alussovsky · Jan 29, 2019

InteGrand said:
$\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!

InteGrand · Jan 29, 2019

alussovsky said:
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.

alussovsky · Jan 29, 2019

InteGrand said:
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!

InteGrand · Jan 29, 2019

alussovsky said:
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$.$

Induction Help (1 Viewer)

alussovsky

Member

InteGrand

Well-Known Member

InteGrand

Well-Known Member

HeroWise

Active Member

alussovsky

Member

alussovsky

Member

InteGrand

Well-Known Member

alussovsky

Member

InteGrand

Well-Known Member

alussovsky

Member

InteGrand

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)