A stronger exact formula makes the induction explicit:For $n=1$, the recurrence gives $S_1=S_0+m=1+m$. For $n\ge 2$, set $j=\lfloor n/2\rfloor$, so $1\le j<n$. In the relevant binary interval, $\lfloor {\log }_{2}j\rfloor =\lfloor {\log }_{2}n\rfloor -1$. The strong induction hypothesis givesFor $n\ge 2$, $S_n\le 1+m+m{\log }_{2}n\le (1+2m){\log }_{2}n$. Hence $S_n=O({\log }_{2}n)$. This is an integer-halving recurrence with constant toll; the separately defined $n=0$ case does not require evaluating $\log 0$.

TakeThe premises hold with constants two and one. ButNo fixed bounding constant can satisfy the proposed conclusion. This proves the failure of unrestricted Big O composition: a constant factor in an inner argument can become an unbounded factor after applying an exponential.

As $x\to +\infty$, big O notation meansThe same constant must work on the entire sufficiently large tail. Absolute values accommodate signed functions. A two-sided convention at infinity would replace $x\ge x_0$ by $|x|\ge x_0$; the positive-integer arguments in the later parts use the positive-tail convention.

The base cases are $13=3(2)+7(1)$, $14=3(0)+7(2)$ and $15=3(5)+7(0)$. Suppose a counterexample exists and choose the least integer $n\ge 13$ failing the claim. It is not one of these base cases, so $n\ge 16$ and $n-3\ge 13$.

Minimality supplies nonnegative integers $x,y$ with $n-3=3x+7y$. Then $n=3(x+1)+7y$, a contradiction. This proof by minimal counterexample establishes the claim. Three consecutive base cases are needed because the reduction subtracts three.

The Euclidean algorithm givesThus the greatest common divisor is $34$. Back-substitution, as in the extended Euclidean algorithm, givesHence $\gcd (306,1394)=34$, with $x=2$ and $y=-9$.

For integers $a,b$ not both zero, replace them first by their absolute values, then repeat integer division:

while b != 0:
    (a,b) := (b, a mod b)
return a

This is the Euclidean algorithm. Its loop invariant is that $\gcd (a,b)$ equals the original greatest common divisor. When $b>0$, the new remainder lies in $[0,b)$, so $b$ is a strictly decreasing nonnegative loop variant. At termination, $\gcd (a,0)=a$, proving correctness, including the case where one original input is zero.

Use the convention that $R\circ S$ applies $S$ first. Reflexivity inserts an identity step: if $aRb$, use $aSa$ to obtain $(a,b)\in R\circ S$; if $aSb$, use $bRb$ for the same conclusion. Thus $R\cup S\subseteq R\circ S$. By monotonicity of relation composition,For strictness, take $A=\{0,1,2,3\}$ and let $R=S$ consist of the identity pairs together with $(0,1),(1,2),(2,3)$. Both are reflexive relations. The left side permits at most two forward chain steps, so does not contain $(0,3)$. The right side permits four steps, including $0\to 1\to 2\to 3\to 3$, so does contain it. Equality therefore need not hold.

One example is the identity function, $f(n)=n$. A second is the permutationBoth are bijections of $\mathbb{N}$, whichever convention includes or excludes zero. For the second, applying $f$ three times returns every input to itself. Thus $f^3=\mathrm{id}$, and composing with the inverse function gives $f^2=f^{-1}$. This permutation cube identity criterion also shows why three-cycles work whereas a nontrivial two-cycle would not.