Suppose that n is odd. Then \(\displaystyle{n}={2}{k}+{1}\), where k is some integer. Furthermore, \(\displaystyle{3}{n}+{1}={3}{\left({2}{k}+{1}\right)}+{1}={6}{k}+{4}={2}{\left({3}{k}+{2}\right)}\)

Since \(3k+2\) is an integer, we conclude that \(3n+1\) is even.

Suppose that \(3n+1\) is even. Then \(3n+1=2l,\)

for some integer l. This also means that

\(\displaystyle{3}{n}={2}{l}-{1}={2}{\left({l}-{1}\right)}+{1}\)

Since \(l-1\) is an integer, we conclude that 3n is odd. Now, if n was even then clearly 3n would also be even, so we get a contradiction. Therefore, n must be odd.