How to use Induction with Sequences?

Question

I have posted this similar question here, but with no hopes. I would just like to know:

Most of the solution I have no issue with. Look at where they say:

"Choose a representation $(n - 3^m)/2 = s_1 + ... + s_k$ in the desired form.

But to do that first, they applied induction to the set:

$$A = \{1, 2, 3, ..., n-1\}$$

You have to ensure,

$$\frac{n - 3^m}{2} \le n-1$$

How do you show that?

Lets, consider the case, $n=5$. It follows,

$$3^1 < 5 < 3^2$$, Hence, $m = 1$ which gives:

$$\frac{5 - 3}{2} \le 4 \implies 1 < 4 \checkmark$$

But the question is how to prove it?

Suppose:

$$\frac{n - 3^m}{2} \le n-1$$

I am to prove:

$$\frac{n + 1 - 3^m}{2} \le n$$

Begin with the hypothesis,

$$\frac{n - 3^m}{2} \le n-1$$

$$\frac{n - 3^m}{2} + \frac{1}{2} \le n- \frac{1}{2} < n$$

Since $n \in \mathbb{N}$

I suppose the statement is proved. Can you check it?

Answer 1

$\frac{n-3^m}{2}\leq n-1$ $\Leftrightarrow$ $n-3^m \leq 2n-2$ $\Leftrightarrow$ $2-3^m\leq n$ $\Leftrightarrow$ $2-n\leq 3^m$, which is clearly true for any $n,m\in\mathbb N$

Answer 2

Recall that $m=\lfloor\log_3n\rfloor$. This means that $m\le\log_3n<m+1$ and hence that $3^m\le n<3^{m+1}$. It follows that $n-3^m<3^{m+1}-3^m$ and hence that

$$\frac{n-3^m}2<\frac{3^{m+1}-3^m}2=\frac{3^m(3-1)}2=3^m\le n\;.$$

That is,

$$\frac{n-3^m}2<n\;.\tag{1}$$

Since we’re assuming in this case that $n$ is odd, we know that $\frac{n-3^m}2$ is an integer, $(1)$ implies that

$$\frac{n-3^m}2\le n-1\;.$$