Question

# Suppose n is an integer. Using the definitions of even and odd, prove that n is odd if and only if 3n+1 is even.

Discrete math

Suppose n is an integer. Using the definitions of even and odd, prove that n is odd if and only if $$3n+1$$ is even.

2021-02-10

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.