## Proof of inequality $\lceil x \rceil \le x+1$

I went through the Master Theorum extension for floors and ceiling section 4.6.2 in the book Introduction to Algorithms

It had the following statement:

Using the inequality $$\lceil x \rceil \le x+1$$

But I haven’t seen the inequality anywhere and could not understand the verifiability of inequality.

Instead the Chapter Floors and ceilings defined floors and ceilings as:

$$x-1 \lt \lfloor x \rfloor \le x \le \lceil x \rceil \lt x+1$$

Please clear my doubt over this.

On how to use this identity and which identity to be considered when because both of them define completely different inequalities.

Thank you.

## A tricky mutual information inequality

Let $$X_0, X_1, X_2$$ be three independently distributed bits, let $$B$$ be a random variable such that $$I(X_0:B)=0$$, $$I(X_1:B)=0$$, and $$I(X_2:B)=0$$, I need to prove that $$I(X_0, X_1, X_2:B)\leq 1$$

(where $$I(M:N)$$ is Shannon’s mutual information).

I can demonstrate that $$I(X_0, X_1, X_2:B)\leq 2$$, by using chain rule of mutual information $$I(X_0, X_1, X_2 : B)= I(X_0:B)+I(X_1,X_2:B|X_0) = H(X_1,X_2|X_0) – H(X_1,X_2|B,X_0) = 2 – H(X_1,X_2|B,X_0) \leq 2$$.

(where $$H(.)$$ is Shannon’s binary entropy).

## Positiveness of two variable inequality

How to show function

g(a, n) =-4a^2+8a^3-4a^4+16an-24a^2n+8a^3n-12n^2-4an^2+12a^2n^2+12n^3-8an^3  

of two variables is positive in a\in (2,n-2) 2 \leq n < infinity. See photo

## Confused in how to insert a slack variable in a constrain inequality

According to my understanding , we should put a slack variable to equate an inequality constrain by inserting the slack varaible in the side that is less than the other side , for example if we have 4x+2<2 this will be 4x+2+slack_variable=2 .But here in Wikipedia :
https://en.wikipedia.org/wiki/Slack_variable In the example section , it says the following “By introducing the slack variable y>=0, the inequality Ax<=b can be converted to the equation y-Ax+b = 0” Which means that the slack variable is inserted in the bigger side ! Please some one explain this confusion.

## How to plot a graphic with solution of some inequality?

I defined the function $$z(n)$$ by

z[n_] := Catch[Do[i; If[Mod[Fibonacci[i], n] == 0, Throw[i]], {i, 100000}]]

and now, I would like to plot the graphic (n,z(n)) for points such that $$z(n)/n<\epsilon$$, for some given value of $$\epsilon>0$$. For instance, for $$\epsilon=0.05$$, I used the command

Catch[Do[n; If[z[n] < 0.05*n, Print[n]], {n,1, 3000}]]

which provides me many values of $$n$$, but I do not know how to make a graphic with them (they appear in some collumn). Thanks in advance.

## Numerical results for Reduce on an inequality

I am trying to determine the regions parameters (Te, ymin) must belong to for a function to be negative for any argument x greater than zero. I have tried using Resolve

       Resolve[         ForAll[x, (a/x^2)*(Log[x - b] + 1) - (a/x)*(1/(x - b)) - (1/         x^2)*(-b^3 + b) < 0] && x > 0, Reals] 

but no expression could be provided. This is not surprising, as I suppose such expression would involve the solution of trascendental equations.

On the other hand, is there a way to get a numerical output from Resolve? For example, a set of (a, b) parameters values on the boundary of the region for which the function is positive?

I thought maybe Nsolve could take an inequality as an expression, but could not find any examples and could not make it work.

A “brute force” alternative I thought about is to create a grid of (a,b) values, and for each couple of values verify if the function is negative along all the positive x-axis (the last step does not seem obvious neither). Is there a maybe more clever way, fully exploiting Mathematica’s capabilities?

I got intrigued by the answer this post, Reduce a complex inequality but I could not make it work for my case, for example

RegionPlot[ ForAll[x, (a/x^2)*(Log[x - b] + 1) - (a/x)*(1/(x - b)) - (1/    x^2)*(-b^3 + b) < 0], {a, 0.01, 0.5}, {b, 0.001,  0.01}] 

does not seem to be correct syntax.

Thanks a lot

## triangle inequality TSP is NP-complete?

I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric TSP problem. So, I wonder how to start a basic approach to prove triangle inequality TSP is NP-complete.

## Changing ContourStyle based on an inequality

I would like to create a bifurcation diagram with ContourPlot. Suppose I want to plot the contour 1-2*a*Q+3*Q^3==0 with a the x-axis, Q the y-axis. I also want linestyle/thickness of the contour plot to change depending on the expression expr = 9*Q^2-2*a. If expr>0, I want it to be dashed; if expr<0, I want it to be a thick line. How to accomplish this?

Some previous posts about similar topic suggested putting an If statement inside the plot, but when I try something like

ContourPlot[If[expr>0, 1-2*a*Q+3*Q^3 == 0], {a,-2,2}, {Q,-2,2}] 

it gives error.

## inequality of distances in a graph

Certainly it’s obvious but I can’t catch the reason behind it.

Why do we have :

Let $$D= (V,A)$$ be a directed graph, $$w:A \to \mathbb R$$ be arc weights and $$s \in V$$. Denote with $$d(s,v)$$ the length of the shortest path from $$s$$ to $$v$$ in $$D$$, subject to $$w$$.

If there are no negative cycles in $$D$$, then we have $$\forall (u,v) \in A : d(s,v) \leq d(s,u) + w(u,v) \iff d(s,v)- d(s,u) \leq w(u,v).$$

Why?

## Inequality for integro-differential system

Reading a paper about homogenization of stochastic coefficients [A. Gloria et al., Invent. math. (2015)], I found the following lemma that gives an estimate of the solution for a given ODE system. The lemma is:

Let $$1\le p,\gamma<\infty$$ and $$a(t),b(t)\ge 0$$. Suppose that there exists $$C_1 <\infty$$ such that for all $$t\ge0$$, $$\begin{gather} \tag{1}\label{eq1} a(t) \le C_1 \left( (t+1)^{-\gamma} + \int_{0}^{t} (t-s+1)^{-\gamma} b(s) \,ds \right), \ b(t)^p \le C_1\left(-\frac{d}{dt}a(t)^p\right). \end{gather}$$ Then there exists $$C_2<\infty$$ depending only on $$C_1,p$$ and $$\gamma$$ such that $$$$\tag{2}\label{eq2} a(t) \le C_2 (t+1)^{-\gamma}.$$$$

My question is: Is it possible to prove a similar result replacing \eqref{eq1} by $$\begin{equation*} a(t) \le C_1 \left( t^{-\gamma} + \int_{0}^{t} (t-s)^{-\gamma} b(s) \,ds \right)? \end{equation*}$$ How would \eqref{eq2} change?