Question

prove the following proposition by induction

Answer 1

Proposition \(3^{n}+1\) is even for all \(n \ge 0\)

Answer 2

Base case : \(3^0+1 = 1+1 = 2(1)\) is even \(\color{green}{\checkmark}\)

Induction hypothesis : Let \(k \in \mathbb{N}\) be an integer greater than \(0\) and assume that the proposition is true for \(n=k\). That is \(3^k+1 = 2q\) for some integer \(q\).

Induction step : \(3^{k+1}+1 = 3^{k+1}+3-2 = 3(3^k+1)-2 = 3(2q)-2 = 2(3q-1)\) is even as desired. \(\blacksquare\)

Answer 3

Thank you that makes a lot more sense than what the book gave.

Just two more questions...
1/ How do I know when to spontaneously turn the 1 into 3-2, they are obviously equal, but where will I get this inspiration from in the future?

2/ What is that black box for at the end? it seems after every proof in the book, they place that black box

Answer 4

for 2/

It is good practice to make the end of a proof with something;
some people use: QED (quod erat demonstrandum), or: \(\square\), \(\blacksquare\) (tombstones)
they all just mean that your at the end of the proof.

Answer 5

even on paper? as in handwritten?

Answer 6

good questions :)
#1 is very hard to answer.. one had to try various things to see that 3-2=1 is useful i gues. but im sure you will get more excellent answers to this question from others...

#2 follow up of unkle's reply :
in proofswe use "." for end of statement. so we need some other way to convey end of proof... we want the reader to know that the proof is completed and no other work is necessary. for that we use QED or that squarebox...

Answer 7

my math teacher in high school used to say QED was Quite Easily Done. Now I know I have been deceived =)

Answer 8

lmao there is a survey result that reveals that >90% of proofs published online contain errors. even the easy looking proofs are not really easy imo. its hard to write a good proof

Answer 9

You just have to notice it. It's not a mandatory "trick" so to speak as he was trying to bring 3^(k+1) to a (3^k + 1)*something in order to use the induction hypothesis.

It is advised (and it looks indeed better) but not mandatory to use the induction hypothesis in order to prove the induction step. In this case, you had to prove that 3^(k +1)+ 1 is always even, regardless of k.

While it is painfully obvious that it is so, the exercise demands that you prove it with induction. So instead of using the normal and painfully obvious method of solving the exercise from the beginning - you use it in the induction step.

For example, one straight forward way to attack the problem is to use the idea of "last digit". It is a known thing (funny enough, it is also easy to prove through induction) that the last digit of any natural number N^k where k takes natural values 1,2,3,4...(to infinity and beyond) are recurring.

In this case, the last digit of 3^k for

k=1 is 3 (3^1=3)
k=2 is 9 (3^2=9)
k=3 is 7 (3^3=27)
k=4 is 1 (3^4=81)
k=5 is 3 (3^5=243)
k=6 is 9 (3^6=729)

and you can see how the (3,9,7,1) is a recurring pattern. Again, it is a "known" thing which can easily be proven and shouldn't theoretically bother any teacher.

Of course, now it is an easy thing to say that since the last digit of 3^k will always be (3,9,7,1) then the last digit of 3^k+1 will always be (4,0,8,2) and such those numbers will always be even.

Suppose you have this method (or any other for that matter) and the exercise demands that you STRICTLY use induction to prove it - you can write this method (or whatever method you choose) in the induction step. In this case, you'd say that 3^(k+1) always has a last digit of (3,9,7,1) and therefore 3^(k+1) +1 will always end in (4,0,8,2) and will therefore be even - without using the induction hypothesis.

Sorry for the long message and all.

Answer 10

np. thankyou tho
I had completely forgotten that the last digit was limited to a set