Mathematical Induction questions

[outkast32]

Are these satisfactory answers?

Question 1: http://i.imgur.com/EElOqwM.jpg

Question 2: http://i.imgur.com/SlE2jza.jpg?1

Thank you :)

 

[Evgeny.Makarov]

Hi and welcome to the forum.

Question 1.

"For some integer $k\ge0$, $5^k-1$ is divisible by 4". Is this the induction hypothesis? You repeat it in the next line, so this line is not necessary.

"then $5^k-1=p$ where $p$ is any integer" $\mapsto$ "then $5^k-1=4p$ where $p$ is some integer".

"since $5^{k+1}-1$ is a multiple of 4" $\mapsto$ "therefore $5^{k+1}-1$ is a multiple of 4".

"4 is divisible by $5^{k+1}-1$" $\mapsto$ "4 divides $5^{k+1}-1$".

Your proof lacks the base case. Also, it is good to show where the induction hypothesis is used.

Question 2.

"$p(x)$ is a polynomial with rational coefficients where $p(x)=a_0+\dots+a_nx_n$ and all $a_i$ are fractions" $\mapsto$ "Let $p(x)=a_0+\dots+a_nx_n$ be a polynomial with rational coefficients".

"Let $M=\dots$ and multiply the polynomial by $M$" $\mapsto$ "Let $M=\dots$. Multiply the equation by $M$".

"So $b_0=Ma_0$, ..., $Ma_n=b_n$ where all the $b_i$ are integers" $\mapsto$ "So $b_0=Ma_0$, ..., $b_n=Ma_n$ are integers".

It is obvious why $c$ is still a root, but it would be clearer if you multiplied the whole equation $p(c)=0$ by $M$.

The rest seems OK.

 

[outkast32]

Thank you for the help!

1 thing, I am confused on the "base case" i understand it supposed to be "easy" and simple, do i just say n = 0? is that it?

How do i write it?

 

[Evgeny.Makarov]

1 thing, I am confused on the "base case" i understand it supposed to be "easy" and simple, do i just say n = 0?

Yes. The problem statement says, "prove that $4\mid(5^n-1)$ for every $n\ge0$". The smallest $n$ for which a proof is required is 0, so the base case consists of proving that $4\mid (5^0-1)$. Of course, $5^0-1=0$, which is divisible by everything (except another 0).

 

[outkast32]

Yes. The problem statement says, "prove that $4\mid(5^n-1)$ for every $n\ge0$". The smallest $n$ for which a proof is required is 0, so the base case consists of proving that $4\mid (5^0-1)$. Of course, $5^0-1=0$, which is divisible by everything (except another 0).

Okay got it! i found a few other mistakes i think.

Does this look good?:

http://i.imgur.com/dtQK8Ed.jpgOr does This way look better?

http://i.imgur.com/BrYvcee.jpg

Anything else?

Thank you so much for helping by the way :)

 

[Evgeny.Makarov]

At the end of the inductive step, you write "Therefore, $5^k-1$ is a multiple of 4". Could you explain why you used the word "therefore"? How does it follow from what comes earlier? In fact, what is the status of this claim: were you proving it, or did you accept it for granted?

The rest seems OK, but I would tweak the style a little. In my opinion, every proof by induction should have the following clearly marked elements.

(1) What I call the induction statement $P(n)$, a propety of natural numbers that you are supposed to prove for all $n$. Writing this property explicitly is important because it makes it easier writing the induction hypothesis and the claim that needs to be proved in the induction step. Besides, in more complicate proofs by induction, the induction statement $P(n)$ may be different from the property $Q(n)$ that appears in the problem statement: "Prove $Q(n)$ for all $n\ge0$". It may happen that $Q(n)$ is too weak for the induction to go through, and one needs to find a suitable strengthening, or generalization. This is a nontrivial step and should definitely be recorded.

(2) The base case (you did this correctly).

(3) The induction step (you have not marked it).

(4) The induction hypothesis (you wrote it, but did not label it as such).

(5) The content of the induction step, i.e., a proof of $P(k+1)$ from $P(k)$. The application of the induction hypothesis $P(k)$ should be clearly marked (you have not done this).

P.S. As a non-native English speaker, I am never sure whether to use "inductive: or "induction" as an adjective. Sorry for any grammatical errors.

 

[outkast32]

At the end of the inductive step, you write "Therefore, $5^k-1$ is a multiple of 4". Could you explain why you used the word "therefore"? How does it follow from what comes earlier? In fact, what is the status of this claim: were you proving it, or did you accept it for granted?

The rest seems OK, but I would tweak the style a little. In my opinion, every proof by induction should have the following clearly marked elements.

(1) What I call the induction statement $P(n)$, a propety of natural numbers that you are supposed to prove for all $n$. Writing this property explicitly is important because it makes it easier writing the induction hypothesis and the claim that needs to be proved in the induction step. Besides, in more complicate proofs by induction, the induction statement $P(n)$ may be different from the property $Q(n)$ that appears in the problem statement: "Prove $Q(n)$ for all $n\ge0$". It may happen that $Q(n)$ is too weak for the induction to go through, and one needs to find a suitable strengthening, or generalization. This is a nontrivial step and should definitely be recorded.

(2) The base case (you did this correctly).

(3) The induction step (you have not marked it).

(4) The induction hypothesis (you wrote it, but did not label it as such).

(5) The content of the induction step, i.e., a proof of $P(k+1)$ from $P(k)$. The application of the induction hypothesis $P(k)$ should be clearly marked (you have not done this).

P.S. As a non-native English speaker, I am never sure whether to use "inductive: or "induction" as an adjective. Sorry for any grammatical errors.

Okay i can label them,

So, for the last line i should not state "therefore" i can erase that.
It just seemed like i should have a therefore, after all the steps in conclusion

How should i phrase it then?

 

[Evgeny.Makarov]

You have not answered the questions I posed:

How does it (i.e., the claim that $5^k-1$ is divisible by 4) follow from what comes earlier? In fact, what is the status of this claim: were you proving it, or did you accept it for granted?

I could write what I think you meant, but I would prefer you re-reading it, thinking about it and answering the questions above.

 

[outkast32]

hmm, because I have shown through the inductive process that 5^k+1 -1 is divisible by 4, and in the base case i took care of the n = 0 because it's not just positive integers, but all natural numbers.

Should it have been therefore 5^k+1 -1 is a multiple of 4.. from the inductive process i was showing above.

So it should be "Therefore, 5^k+1 -1 is a multiple of 4 because 4 divides (5^k+1 -1) and it is true for every n >=0.

Or maybe I am confused by the k and n.. Should i somewhere be saying "therefore 5^n-1 is divisible by 4.. and it is true for every n >=0" because that's what I am trying to actually prove

 

[Evgeny.Makarov]

Should it have been therefore 5^k+1 -1 is a multiple of 4.. from the inductive process i was showing above.

Yes (and please use parentheses in 5^(k+1) because exponentiation is performed before addition). It is this that you have shown in the inductive step and not $4\mid(5^k-1)$. The latter fact you assumed as the inductive hypothesis. It would be funny to switch what you assume with what you need to prove, don't you think?

So it should be "Therefore, 5^k+1 -1 is a multiple of 4 because 4 divides (5^k+1 -1) and it is true for every n >=0.

The phrases "$5^{k+1}-1$ is divisible by 4" and "4 divides $5^{k+1}-1$" mean exactly the same thing, so there is no need to use both. I would conclude the step as follows. "Therefore, $5^{k+1}-1$ is divisible by 4, which concludes the inductive step. By induction, it follows that $5^{n}-1$ is divisible by 4 for all $n\ge0$.

 

[outkast32]

Yes (and please use parentheses in 5^(k+1) because exponentiation is performed before addition). It is this that you have shown in the inductive step and not $4\mid(5^k-1)$. The latter fact you assumed as the inductive hypothesis. It would be funny to switch what you assume with what you need to prove, don't you think?

The phrases "$5^{k+1}-1$ is divisible by 4" and "4 divides $5^{k+1}-1$" mean exactly the same thing, so there is no need to use both. I would conclude the step as follows. "Therefore, $5^{k+1}-1$ is divisible by 4, which concludes the inductive step. By induction, it follows that $5^{n}-1$ is divisible by 4 for all $n\ge0$.

Ahh, i see where i went wrong :)

thank you so much sir! have a good day!