1
$\begingroup$

How to prove $T(n)$ is a monotonically increasing function by induction provided that $T(n) = T(n/2 + \sqrt{n}) + \sqrt{6046}$?

$n$ is larger than $n/2 + \sqrt{n}$ when $ n \geq 5$ and it is obvious that $T(n) > T(n/2 + \sqrt{n})$. Thus, $T(n)$ is monotonically incresing from $n/2 + \sqrt{n}$ to $n$ and so on. However, as $n$ get larger there are also larger gaps between $n/2 + \sqrt{n}$ and $n$. How could I prove $T(n+1) > T(n)$ for any $n \geq 5$? Any hint will be helpful.

  • 0
    It's a problem in the first assignment of MIT OpenCourse Introduction to Algorithm2012-02-18

2 Answers 2

2

We use strong induction, also known sometimes as course of values induction. This version of mathematical induction comes up very often in Computer Science arguments (and elsewhere, like Number Theory). Any strong induction argument can be mechanically recast as an ordinary induction argument, but the strong induction approach is often more natural.

Assume that we know, for a specific natural number $n$, that $T(k+1)>T(k)$ for every natural number $k< n$. We show that $T(k+1)>T(k)$ for every natural number $k < n+1$.

Obviously we only need to prove that $T(n+1)>T(n)$. This almost follows from the induction hypothesis, since $T(n+1)=T((n+1)/2+\sqrt{n+1})+\sqrt{6046}$ and $T(n)=T(n/2+\sqrt{n})+\sqrt{6046}$, and by the induction hypothesis, $T((n+1)/2+\sqrt{n+1})>T(n/2+\sqrt{n})$.

But we must be able to assume that $(n+1)/2+\sqrt{n+1}>n/2+\sqrt{n}$. This last inequality is obviously true in the reals. However, if we are going to do rounding, and "$k/2+\sqrt{k}$" is not really $k/2+\sqrt{k}$, all bets are off, and we can only conclude that $T(n+1)\ge T(n)$. There may not be a change when we increment $n$ by $1$, but if there isn't, there will be a change when we increment $n$ once more.

Remark: Let's illustrate the rounding issue numerically. Let $n=50$. Then $n/2+\sqrt{n}\approx 18.1$ and $(n+1)/2+\sqrt{n+1}\approx 18.7$. If we use the greatest integer function, these both become $18$, so $T(26)=T(27)=T(18)$. It is easy to come up with a similar example for which using the nearest integer function has similar issues.

  • 0
    @manuzhang: Sorry, no time. Check until $n/2+\sqrt{n}$ is less than $n$. That's where things really start.2012-02-19
0

Well, here's my own proof by adding basis step to @André Nicolas's answer and handling the real number issue. Assume that all real numbers are rounded to the nearest integer though this is not given in the original problem. I'll prove $T(n)$ is a monotonically increasing function for $n \geq 5$ since that's when $n > n/2 + \sqrt{n}$.

Basis Step:
When $n = 6$, $ n/2 + \sqrt{n} \approx 5$. It follows that $T(6) = T(5) +\sqrt{6046}$ and $T(6) > T(5)$, which completes the basis step.

Induction Hypothesis(exactly that of @André Nicolas's):
Assume that we know, for a specific natural number $n$, that $T(k+1) > T(k) $ for every natural number $5 \leq k.

Induction Step:
For every $5 \leq k < n+1$, $5 \leq$ round [$k/2 + \sqrt{k}$] $ < n$.
If round[(k+1)/2 +\sqrt{k+1}] > round[$k/2 + \sqrt{k+1}$], then it follows directly from induction hypothesis that $T(k+1) > T(k)$;
if round[$(k+1)/2 +\sqrt{k+1}] =$ round[$k/2 + \sqrt{k+1}$], then $T(k+1) = T(k)$. However, we can still get $T(k+2) > T(k)$ because round[(k+2)/2 +\sqrt{k+1}] > round[$k/2 + \sqrt{k+1}$].
In both cases, it holds that $T(n)$ is a monotonically increasing function.