Problem Solving, Part 2

From my last post, I have decided to try to prove:

For each natural number n there exists a natural number m such that F(m,n) = 1.

Using the definition of F(m,n) found in the previous post.

It may help to analyze the behaviour of F right as it reaches 1. The only way for the f(x) = 1 is if x = 2. This is because there is no odd positive integer n such that 3n + 1 = 1. For the same reason, the only way for f(x) = 2 is if x = 4. It is also worthwhile to note that f(1) = 4, since 3(1)+1 = 4. So, once 1 is reached (if it ever is), the function F(m, n) will follow the sequence: {4,2,1,4,2,1,4,....} as m increases.

We've also established that in cases where n is not 1, 2 (and these cases are trivial anyways), F(m,n) will reach 4 before it reaches 1. But, since n != 1, the only way that f(x) = 4 is when x = 8. A pattern seems to be emerging based off the definition of the function. Note that, in the case that n is even:

f(n) = n/2.

All powers of 2, 2^x, can be expressed by 2*2*2....*2*1, where the number of 2s is x. Therefore, 2^x/2 will continue to be even, until the number 1 is reached. This leads to the following claim:

P(n):  F(n, 2^n) = 1
Which can be proven for all n using induction:

Base case: n = 0
Then 2^0 = 1, so applying the function 0 times will yield 1.

Base case: n = 1
Then f(2^1) = 1. So F(1, 2^1) = 1.

Induction step: Assume P(n)
Note that 2^(n+1) is even, and f(2^(n+1)) = 2^(n+1)/2 = 2^n

So F(n+1, 2^(n+1)) = F(n, 2^n) , which, by the induction hypothesis, is equal to 1.

So the claim is true for all n.

From this, we can change the initial claim that we are trying to prove to:

For each natural number n there exists a natural number m such that F(m,n) is a power of 2.

Next, I will actually try to prove this statement indirectly by assuming the negation and attempting to produce a contradiction