Use induction 2. The Collatz Conjecture Let f : Z++ be the function defined by 3

Question

Use induction

2. The Collatz Conjecture Let f : Z++ be the function defined by 3r +1, x is odd (a)x/2 is even The famous Collatz Conjecture states that if we start with any positive integer, and repeatedly apply f, then we must eventually reach the number 1. For example, suppose we start with the number 23 f (20) 20/2 10; f (10) 10/2 5; f (5) 3.51 16; f (16) 16/2 -8; f(8) 8/2-4; f (4) 4/2-2; f (23) 3 23+170; f (70) 70/2 35; f (35) 3.35 1- 106; f (106) 106/2 53; f (53) -3 53 +1-160; f (160) 160/2 - 80; f (80) 80/2 40; f (40) 40/2 20; Hence, after applying f fifteen times, we reached the number 1. The Collatz Conjecture says that this will always eventually happen, no matter which number we start with. The

Explanation / Answer

Let us prove the above function g(x) eventually reaches 1 by INDUCTION

For x = 1

g(1) = 2, Now g(2) = 1 [reached one]

Let us assume that g(k) < k

Now, for g(k+1)

Let us assume that, k is odd, => k+1 will be even, thus g(k+1) = (k+1)/2 which is less than k+1

Now, if k is even, => k+1 wil be odd => g(k+1) = k+2, now g(k+2) = (k+2)/2 < k+1

Hence Proved by induction!

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.