Show that $S(n)\leq5\log_2(2n)+7$

Question

I'm asked to show that for any positive integer n, we have: $S(n)\leq 5\log_2(2n)+7$

Where $S(n)$ is a total function (spans from positive integers to real integers),

such that $S(1) = 7$, and $S(2^k) = S(2^{k-1})+5$

$S(n) \leq 5\log_2(2n)+7$

I'm not exactly sure how to approach this. I'm not sure a proof by induction would be viable here (Don't think that's what the questions wants me to do). And I'm not sure if I can simply just plug in values, and show that positives values for n work in that sense? Any help would be much appreciated.

Answer 1

Let us first determine the sequence for $S(n)=S(2^k)$. By knowing that $S(1)=7$ and $2^0=1$, we can find a way to determine the sequence for $S(n)$ using the recursive sequence $S(2^k)=S(2^{k-1})+5$ for which $k\in\mathbb{Z}$ (note that we are using $k$ right now not $n$):

if $k=1$,

$$\begin{align} S(2^1)=S(2^{1-1})+5 \\ S(2)=S(1)+5 \\ S(2)=7+5 \\ =12.\end{align}$$

From know in that now $S(1)=7$ and $S(2)=12$, we are able to form an arithmetic sequence for $S(n)$. If we continued beyond $n=2$ for $S(n)$, we can see that we get this:

if $k=2$,

$$\begin{align} S(2^2)=S(2^{2-1})+5 \\ S(4)=S(2)+5 \\ S(4)=12+5 \\ =17;\end{align}$$

if $k=3$,

$$\begin{align} S(2^3)=S(2^{3-1})+5 \\ S(8)=S(4)+5 \\ S(8)=17+5 \\ =22;\end{align}$$

if $k=4$,

$$\begin{align} S(2^4)=S(2^{4-1})+5 \\ S(16)=S(8)+5 \\ S(16)=22+5 \\ =27.\end{align}$$

We can now see that the sequence for $S(2^k)$ is in the form of $$n_1,n_2,n_4,n_8,n_{16},\cdots$$ and with the values $$7,12,17,22,27,\cdots.$$

So we can determine a sequence first for $S(2^k)$:

$$d=n_2-n_1=12-7=5$$

$$S(2^k)=n_1+(n-1)d$$ $$S(2^k)=7+(n-1)5$$ $$S(2^k)=5n+2.$$

We can then determine the sequence for $S(n)$ that would make an arithmetic function for $n$ such that since we were using a function of $k$ before this, $n=2^k$:

$$k=\log_2n$$ $$S(\log_2n)=5n+2=S(2^k).$$

To get the pure function for $S(n)$, we must get rid of the "$\log_2$" in the "$S(\log_2n)$" by knowing that the sequence is just transformed:

$$S(\log_2n)=5n+2$$ $$S(n)=5\log_2(n)+2.$$

From this new $S(n)$-equation, we can plug it the inequality and see that it is true for all positive integers $n$:

$$S(n)=5\log_2(n)+2$$ $$\therefore 5\log_2(n)+2\leq5\log_2(2n)+7, \ \forall{n}\in\mathbb{Z}.$$

$\boxed{Q.E.D.}$

Answer 2

First, I suggest that you solve the relation $S(2^k) = S(2^{k-1})+5$, such that you have only one $S$ term. You can do that by substituting $S(2^k)$ recursively.

Solution:

$S(2^k) = S(2^{k-1})+5$ or,

$S(2^k) = (S(2^{k-2})+5) + 5$ or,

$S(2^k) = ((S(2^{k-3})+5) + 5) + 5$. This goes on until we reach the "base"

case where $S(2^k) = 5k + S(2^0) = 5k + 7$.

Now we know that any positive real number can be represented by $2^k$; because, we can equate $a = 2^k$, and thereby we can say that $k = log_2(a)$.

So lets put $n = 2^k$ in the expression $S(n)\leq 5\log_2(2n)+7$ to get $S(2^k)\leq 5\log_2(2^{k+1})+7$ which is,

$5k + 7 \leq 5(k+1) + 7$

Now we have the above as our final expression, and I guess it is obviously true, for all positive values of $k$.

Update:

@stochasticboy3217, you are right. But taking closer look at the problem shows that there isn't enough information to conclude the answer for it, because, the information $S(2^k)=S(2^{k−1})+5$ only shows how the function behaves for a discreet domain region. The only given base condition is, $S(1) = 7$, but to be able to arrive at a relation for the domain $\forall k \in \mathbb{Z}$, the given information is not enough (as here the domain is $1, 2, 4, 8, 16,...$). Note that, unless we have a complete relation for $S(n), n\in (0, 1]$, as a given function we cannot conclude the answer.

$S(k)=5k + 7$ is only valid for positive integer values of $k$. But becomes invalid if we assign a non-integer value for $k$. The reason is, the main information we exploit to find this answer is $S(2^k) = S(2^{k-1})+5$. Here, if we consider $k$ to not be a positive integer, then we can never arrive at the base case, and the given base condition $S(1) = 7$ is no longer useful. Because, as @stochasticboy3217 pointed out, if we choose $k=1.584$ or something, we can never arrive at the result. So there is literally no logical way to determine $S(k)$, without involving the term $S(2^{k−1})$.

But we can easily arrive at a result which holds for the interval $k = 2^n, \forall k\in \mathbb{Z}^+$, which is same as the result I came up with: $5k + 7 \leq 5(k+1) + 7$.

So we finally have, $S(2^k) = 5k + f(k)$, where $f(k)$ denotes $S(frac(k))$ for values of $k\in (0, 1)$ and $f(1) = 7 = S(1)$ (as given). Here, $frac(.)$ represents the fractional part.

So we cannot know the answer unless $f(k)$ for the fractional part is defined.