Codex @codex  0

Explore the family tree one individual at a time, maintaining a queue of individuals not yet explored. Initially its size is $Y_0=1$. Exploring individual $t$ removes it and adds its independent offspring $Z_t$, so before the queue empties,One may define the independent increments indefinitely, but the tree exploration stops at $T=\inf \{t:Y_t=0\}$. This hitting time is the total progeny, including the ancestor. Since each increment is at least $-1$, a queue cannot jump below zero before hitting zero. If it never hits zero, the family has infinitely many individuals.

Suppose $kp<1$. A Chernoff bound in moment-generating-function form says that for independent $W_j$ and $\theta >0$,Here take $W_j=Z_j-1$, withWe have $M(0)=1$ and $M^{\prime }(0)=kp-1<0$, so some $\theta >0$ has $M(\theta )<1$. Let $c=-\log M(\theta )>0$. If $T>n$, the queue is still positive after $n$ explorations; its integer value is at least one, giving ${\sum }_{j=1}^n(Z_j-1)\ge 0$. ThereforeThis proves the claimed bound without appealing to a general branching-process tail theorem.

The argument proves the more general exponential total progeny tail for bounded subcritical offspring.

The Ramsey number $R(s,t)$ is the least integer $N$ such that every graph on $N$ vertices contains either a clique of size $s$ or an independent set of size $t$. Equivalently, every red-blue colouring of the edges of $K_N$ contains a red $K_s$ or a blue $K_t$.

Put $a=R(s-1,t)$, $b=R(s,t-1)$ and consider a graph on $a+b$ vertices. Fix a vertex $v$. If it has at least $a$ neighbours, their induced graph contains either a clique of size $s-1$, which together with $v$ gives a clique of size $s$, or an independent set of size $t$. Otherwise $v$ has at least $b$ nonneighbours. Their induced graph contains either a clique of size $s$, or an independent set of size $t-1$, which can be enlarged by $v$. ThusSince $R(2,3)=R(3,2)=3$, this gives $R(3,3)\le 6$. For the reverse bound, the five-cycle has no triangle and no independent set of size three: its complement is again a five-cycle, so it too is triangle-free. Hence the property fails on five vertices and

For disjoint nonempty sets $X,Y$, let $e(X,Y)$ count edges between them. Their edge density isThe pair is $\epsilon$-regular if every $A\subseteq X$ and $B\subseteq Y$ with $|A|\ge \epsilon |X|$, $|B|\ge \epsilon |Y|$ satisfies $|d(A,B)-d(X,Y)|\le \epsilon$.

An $\epsilon$-regular partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering $V(G)$, with $|V_0|\le \epsilon |V(G)|$, equal positive sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$ with $1\le i<j\le k$ that are not $\epsilon$-regular. The set $V_0$ is exceptional and its pairs need not satisfy regularity.

Szemerédi regularity lemma states that for every $\epsilon >0$ and integer $m_0\ge 1$, there are integers $M,n_0$ such that every graph with $n\ge n_0$ vertices has such a partition withThe bounds depend on $\epsilon ,m_0$, not on the graph order. Using a strict regularity inequality or a slightly different constant in the allowed pair count gives an equivalent conventional version; the displayed convention will be used below.

For a finite graph $G$, its chromatic polynomial $p_G(x)$ is the polynomial whose value at each positive integer $q$ counts proper vertex colourings of $G$ from a fixed palette of $q$ labelled colours. Adjacent vertices must receive different colours, and unused colours are allowed.

For an edge $e=uv$, the deletion-contraction recurrence for the chromatic polynomial isHere $G-e$ deletes only the edge $e$, while $G/e$ performs edge contraction, identifying $u,v$ and removing $e$. Any parallel edges produced by edge contraction can be replaced by a single edge, since their constraints on proper vertex colourings are identical.

Indeed, the proper vertex colourings of $G-e$ in which $u,v$ differ are precisely those of $G$, while those in which $u,v$ agree correspond bijectively to proper vertex colourings of $G/e$. This proves the equality for every positive integer $q$, hence as a polynomial identity. Together with $p_G(x)=x^{|V(G)|}$ for a graph without edges, the recurrence also proves by mathematical induction that the counting function is a polynomial.

Let the nonempty connected components of a graph of $G$ be $G_1,\dots ,G_t$. A proper vertex colouring can be chosen separately on each connected component of a graph, since no edge joins different connected components of a graph. The multiplication principle gives, first at positive integers and then as a polynomial identity,It remains to justify that every factor has zero constant term. More generally, for every nonempty simple graph $H$, prove $p_H(0)=0$ by mathematical induction on the number of edges. If there are no edges, then $p_H(x)=x^{|V(H)|}$ with $|V(H)|\ge 1$. Otherwise choose an edge $e$. Both $H-e$ and the simplified edge contraction $H/e$ are nonempty graphs with fewer edges. The deletion-contraction recurrence for the chromatic polynomial and mathematical induction giveThus $p_{G_j}(x)=x{q}_j(x)$ for a polynomial $q_j$, andFor the empty graph, $t=0$ and $p_G(x)=1$, so the conclusion also holds. This is the chromatic polynomial product over components.

Write $V=V(G)$ and $E=E(G)$. For $F\subseteq E$, let $c(F)$ denote the number of connected components of a graph of the spanning subgraph $(V,F)$, including isolated vertices. The inclusion-exclusion principle, applied to the unwanted events that the two endpoints of an edge receive the same colour, gives the chromatic polynomial inclusion-exclusion formulaTo justify the exponent, imposing equal colours across all edges in $F$ forces a single colour on each connected component of a graph of $(V,F)$, with independent choices between its connected components of a graph. Thus the corresponding count at $q$ colours is $q^{c(F)}$. Equality for all positive integers proves the polynomial identity.

Fix an index $i$ in the stated range. A subset $F$ contributes to the coefficient of $x^{n-i}$ exactly when $n-c(F)=i$. If $(V,F)$ contains a graph cycle of length $s$, the hypothesis gives $s\ge \ell$. All its $s$ vertices lie in one connected component of a graph. For any connected component of a graph $D$, its contribution to $n-c(F)$ is $|V(D)|-1$, soThis contradicts $i\le \ell -2$. Therefore every contributing $(V,F)$ is a forest. The forest identity $|F|=n-c(F)$ then gives $|F|=i$.

Conversely, every $i$-edge subset is a forest, since a graph cycle in it would have at most $i<\ell$ edges. It therefore has $c(F)=n-i$ and contributes exactly $(-1{)}^i$. There are $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ such subsets, by the definition of a binomial coefficient. ConsequentlyHere the coefficient notation is understood within the defined indices $0\le i\le n$; if the displayed range is extended past $n$, the coefficients beyond the constant term can be set to zero. For a forest, $m\le n-1$, so the binomial coefficients there are also zero. The key reason girth determines initial chromatic coefficients is that a graph cycle can affect only exponents whose loss of connected components of a graph is at least $\ell -1$.

The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices $x,y$ of a finite graph, the maximum number of internally vertex-disjoint paths from $x$ to $y$ equals the minimum size of an $x$–$y$ vertex separator.

Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.

Here is the reduction, including the correspondence with vertex separators. Put $N=|V(G)|$. Perform vertex splitting on each vertex $v\ne x,y$, replacing it by $v_{\mathrm{in}},v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of flow network edge capacity one. Keep $x$ as the source and $y$ as the sink. For each original undirected edge $uv$, put directed edges from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of flow network edge capacity $N$; an unsplit endpoint uses $x$ or $y$ itself.

A family of $p$ internally vertex-disjoint paths gives a feasible integral flow of value $p$, by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in $G$ are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.

Deleting a vertex separator $S$ corresponds to removing its split edges, of total flow network edge capacity $|S|$. This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most $|S|$. Thus the minimum cut capacity is no greater than the minimum vertex separator size.

For the reverse inequality, deleting all $N-2$ internal vertices separates $x,y$, because they are nonadjacent. Hence a minimum cut has cut capacity at most $N-2<N$ and cannot contain a directed edge of flow network edge capacity $N$. Its outgoing edges are therefore split edges. Let $S$ be the original vertices associated with them. Any $x$–$y$ graph path avoiding $S$ would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence $S$ is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.

The passage belongs to the English reception of Euclid's number theory. Henry Billingsley's The Elements of Geometrie by Henry Billingsley, published in 1570, brought the Elements into English with extensive explanatory material. The original title page advertises translation and annotations; the extract's worked examples show what explanatory prose could add to a compact definition. Henry Billingsley's numbering calls this Definition 23 of Book VII; the familiar modern numbering is VII, Definition 22. The difference is editorial, not a difference in the perfect number being defined.^[ref][ref]

Here a number's parts are its positive proper divisors, rather than arbitrary pieces of a sum or all smaller integers. In modern notation the definition iswhere $\sigma$ is the sum-of-divisors function. Thus $12$ is not a perfect number: its positive proper divisors total $1+2+3+4+6=16$. It is essential to exclude $n$ itself: including it would double the required sum. The pairing of a divisor $d$ with the fraction $1/(n/d)$ of the whole explains the extract's language of halves, thirds and so on. Its examples are complete checks because they identify every positive proper divisor, not merely some convenient decomposition.

The larger mathematical context is the construction in Book IX, Proposition 36. If $q=2^p-1$ is a prime number, then $N=2^{p-1}q$ is a perfect number. To reconstruct the argument, prime factorization gives all its divisors as $2^j$ and $q{2}^j$, with $0\le j\le p-1$. A finite geometric series therefore givesThe choices $p=2,3,5,7$ produce $6,28,496,8128$. The primality assumption matters: choosing $p=4$ produces $120$, whose sum-of-divisors function is $360$, not $240$. The construction gives a reason for the examples and connects perfect numbers with Mersenne primes.^[ref]

The extract itself supplies a definition and examples, not a classification or a mathematical proof that such numbers are rare. In particular, the converse that every even perfect number has this form belongs to the later Euclid-Euler theorem; it should not be read back into this passage. The historically significant feature is the transmission of deductive arithmetic through vernacular explanation: a book called geometry also teaches the divisibility theory needed for a general construction.

Heinrich Weber's 1882 paper concerns prime numbers represented by quadratic forms. Its definition abstracts a finite group from the nature of its elements: what matters is a closed binary operation, associativity, and left and right cancellation laws. Here degree $h$ means the number of elements, now called the group order; it is not the number of letters acted on by a permutation group. This matters when relating the passage to earlier work on substitutions. The definition fits the use of groups of classes of quadratic forms, where the elements are already mathematical objects more elaborate than individual permutations.^[ref][ref]

The apparent omission of an identity element and inverse elements is not fatal. Every nonempty finite cancellative semigroup is a group. Here is a proof identifying exactly where the assumption of a finite set enters. For fixed $a\in G$, the maps $L_a(x)=ax$ and $R_a(x)=xa$ are injective by cancellation. An injective function from a finite set to itself is surjective, so choose $e$ with $ae=a$. For every $x$,and left cancellation gives $ex=x$. To show $e$ is also a right identity element, useRight cancellation gives $xe=x$. Thus the same $e$ works on both sides for every $x$; it has not merely been chosen as an element fixing $a$.

Surjectivity now gives $b,c$ with $ab=e$ and $ca=e$. By associativity,So $b$ is a two-sided inverse element of $a$. Since $a$ was arbitrary, the usual group axioms follow. The nonempty hypothesis is tacit in a system of $h$ elements intended to have positive $h$: the empty system would satisfy the displayed universal conditions vacuously but would have no identity element.

The infinite case exposes the force of the qualification. The positive integers under addition are closed, associative and cancellative, but have no additive identity element. Even the nonnegative integers have an identity element without additive inverse elements for positive elements. The failure is precisely that injective functions of an infinite set to itself need not be surjective. Heinrich Weber's conditions are therefore not an unrestricted replacement for the modern group axioms.

Historically the abstraction is important because it allows arguments to be applied across different kinds of elements. An assumption of commutativity is absent: class-group applications do not make commutativity part of the general definition. For example, the symmetric group $S_3$ meets the conditions but is noncommutative. The definition also does not require a prior presentation as permutations, although Cayley's theorem provides such a representation. The passage documents the separation of an algebraic structure from any one representation of it, with finiteness carrying logical work that later axiom systems usually assign to explicit identity element and inverse element axioms.

Standards of mathematical proof changed between the seventeenth and nineteenth centuries because both the objects studied and the operations performed on them changed. A finite geometrical construction, an infinite expansion, and an abstract group raise different questions about justification. There was no universal seventeenth-century indifference to rigour followed by its sudden nineteenth-century invention. The more defensible thesis is that successful methods repeatedly exposed unstated assumptions; later work made some of those assumptions into explicit definitions, hypotheses and existence arguments.

Pierre de Fermat's adequality illustrates the distinction between an effective method and its justification. For $F(a)=a(L-a)$, comparing neighbouring expressions givesDividing by $e$ and suppressing the remaining term in $e$ produces $a=L/2$. There is an independent finite verification:Thus the result can be secure even when the general procedure raises a question: why is the increment first nonzero for division and then discarded? In the parabola construction of question 2, the same issue appears in replacing a strict geometrical comparison by adequality and extracting the subtangent. A historical explanation must describe this operation on its own terms rather than silently equate it with a modern derivative.^[ref]

Isaac Newton and Gottfried Wilhelm Leibniz supplied different languages for the new calculus. Isaac Newton's Introduction to the Quadrature of Curves by Isaac Newton, first published with the 1704 Opticks, presents quantities generated by motion and considers their rates of change. Its mature language of first and last ratios seeks exact relations as increments vanish; it should not be confused with simply asserting that a small error is harmless. Gottfried Wilhelm Leibniz's 1684 Nova methodus pro maximis et minimis by Gottfried Wilhelm Leibniz presents a calculus of differentials and operational rules. Their common problem was to explain why procedures using vanishing increments establish exact results, while their chosen objects and modes of explanation differed.^[ref][ref]

George Berkeley's The Analyst by George Berkeley (1734) exposes the logical pressure point. For the cube,The finite identity does not become a legal division at $h=0$. The modern repair is to keep $h\ne 0$ throughout the identity and prove that its right-hand side tends to $3x^2$. That limit is different from a quotient evaluated at zero. George Berkeley's criticism therefore concerns the grounds of inference, not whether the established rules often produce correct answers. His theological polemic also reminds us that standards of mathematical proof could be contested outside specialist calculation.^[ref]

The infinite introduced another burden. Joseph Fourier's 1822 use of trigonometric series to represent arbitrary functions greatly extended what calculations in mathematical physics could express. But deriving Fourier coefficients by orthogonality only shows what those coefficients must be if the proposed operations are legitimate. It does not prove convergence, equality with the initial data, or interchange of an integral and an infinite sum. The example of a constant expanded in a Fourier sine series makes a hidden qualification visible: the terms all vanish at the endpoints, even when the assigned data do not. The correct theorem must specify the domain and mode of representation.^[ref]

Peter Gustav Lejeune Dirichlet's 1829 memoir supplies a particularly precise example of changing proof obligations. It criticises a convergence argument of Augustin-Louis Cauchy's which used complex substitution into an arbitrary function and an insufficient comparison between signed series. Peter Gustav Lejeune Dirichlet supplies the instructive pairThe first series converges by the alternating series test; the second diverges because their difference is the harmonic series. Nevertheless $b_n/a_n=1+(-1{)}^n/\sqrt{n}\to 1$. Thus asymptotic equality of terms does not transfer convergence between conditionally convergent signed series. A comparison principle valid for positive terms needs additional justification when cancellation is involved. The example refutes a mode of inference rather than merely correcting a numerical answer.^[ref]

Augustin-Louis Cauchy's own foundations programme is part of this change. The 1821 Cours d'analyse by Augustin-Louis Cauchy makes limits, continuity and series convergence central to elementary reasoning. Yet its Sum theorem of Cauchy also shows why announcing rigour does not make every proof adequate. In modern terminology, continuous functions can have a discontinuous pointwise limit. An explicit series version isEach term is a polynomial and the partial sum is $x-x^{N+1}$. The convergence does not hold in uniform convergence: with $x_N=1-1/N$, the error $x_N^{N+1}$ tends to $e^{-1}$ rather than zero. The modern uniform limit theorem repairs the inference by requiring one bound on the error to work throughout the domain. This example diagnoses the missing control under a pointwise reading; it does not settle every historical interpretation of Augustin-Louis Cauchy's infinitesimal language.^[ref]

The issue is the order of dependence in quantifiers. Pointwise convergence permits the threshold $N$ to depend on both the error tolerance and the point. Uniform convergence requires a threshold depending only on the tolerance. If $f_N$ is continuous near $x_0$ and the convergence is uniform, choose $N$ so that $|f-f_N|<\epsilon /3$ nearby, then use the continuity of this fixed $f_N$ to make $|f_N(x)-f_N(x_0)|<\epsilon /3$. The triangle inequality proves $|f(x)-f(x_0)|<\epsilon$. Writing out this proof reveals what a vague statement that the tail is small leaves unproved.

Another nineteenth-century development concerns the foundations of the real numbers themselves. Richard Dedekind's Continuity and Irrational Numbers by Richard Dedekind (1872) asks for an arithmetical account of the continuity often borrowed from a drawn line. A Dedekind cut separates the rational numbers into lower and upper classes. For instance,defines a gap in the rational numbers corresponding to $\sqrt{2}$. The cut is determined without assuming that a rational number fills it. The extended number system then supports existence theorems that a geometrical picture alone had suggested.^[ref]

This matters for apparently elementary proofs. Suppose $f$ is continuous on $[a,b]$ with $f(a)<0<f(b)$. Repeated bisection constructs nested intervals whose endpoint values have opposite signs and whose lengths tend to zero. To conclude that there is a common limiting point, one needs the completeness of the real numbers. Continuity then forces its value to be zero. Over the rational numbers, $f(q)=q^2-2$ changes sign between $1$ and $2$ but has no rational zero. Thus even a proof that avoids pictures must explain the existence of its limiting object. Richard Dedekind's account makes that requirement an explicit part of the mathematical setting, rather than an intuition about a continuous line.^[ref]

There is a parallel change in algebra. Heinrich Weber's 1882 definition in question 6 describes arbitrary elements through laws of composition. To assess such a definition one proves implications between axioms. The passage's finite set hypothesis implies that cancellative multiplication has an identity element and inverse elements; without that hypothesis, the positive integers under addition supply a counterexample. This is a new kind of proof obligation: one must establish that a proposed abstract definition has the intended consequences, rather than rely on their familiarity in particular numerical or permutation examples.^[ref]

The principal change was towards explicit control of operations, hypotheses and existence. Effective symbolic algorithms persisted, and geometric reasoning remained valuable. What became increasingly demanding was the passage from success in examples to a general claim: an infinitesimal step needed justification, an infinite expansion needed a convergence theorem, a limiting point needed a complete number system, and an abstract definition needed its consequences proved. The examples also prevent a simple progress story: nineteenth-century mathematicians disagreed about admissible reasoning, and a programme devoted to rigour could itself become the object of a successful critique.

A totally unimodular matrix has the property that every square submatrix has determinant zero, one or minus one. This includes the one-by-one submatrices, so every entry belongs to $\{0,1,-1\}$.

Its importance is integrality of linear-programming vertices: if $A$ is totally unimodular and $b$ is integral, every vertex of $\{x:Ax\le b,x\ge 0\}$ is integral. Adding rows of the identity preserves total unimodularity. A nonsingular active basis therefore has determinant $\pm 1$ and an integer inverse by the cofactor formula, making its basic solution integral. Thus a finite optimum attained at a vertex of the linear programming relaxation gives an integer optimum without branching.

One sufficient condition is: entries belong to $\{0,1,-1\}$, each column has at most two nonzero entries, and any column with two has one $+1$ and one $-1$. This is the signed column condition for total unimodularity, satisfied by directed vertex-edge incidence matrices. It is sufficient, not necessary.

The constraints give the valid upper boundFor example $(x_1,x_2,x_3,x_4)=(0,1,3,4)$ satisfies every constraint: the first left side is four, the next three are three, five and two, and $x_4\ge 1$. Its objective is eight. Hence the upper bound is attained by an integer point, provingAll optimal solutions can also be identified. Equality forces $x_1=0$, $x_3=3$ and $x_2+x_4=5$. The remaining constraints reduce to $x_2\ge 1$ and $x_4\ge 1$. Thus exactly four integer optima occur:This is an optimality certificate by a valid relaxation bound and a feasible integer solution; no assumption of total unimodularity is needed. The source's ${\mathbb{Z}}_{+}$ denotes nonnegative integers, as is also necessary for its assignment equations in the next question.

The retained integer assignment constraints have only two feasible matrices,Their $(a\cdot x,b\cdot x,c\cdot x)$ totals are $(4,5,10)$ and $(3,6,8)$ respectively. For nonnegative Lagrange multipliers $\lambda ,\mu$, add $\lambda (3.5-a\cdot x)+\mu (5.5-b\cdot x)$ to the maximization objective. Each feasible point gains a nonnegative amount, so maximizing over the retained assignment set gives an upper bound:The Lagrangian dual problem minimizes this convex piecewise-linear function over $\lambda ,\mu \ge 0$. Put $d=\lambda -\mu$; every real $d$ can occur. The two affine terms average to nine, so their maximum is at least nine, with equality exactly when $d=2$. ThusNeither integer assignment satisfies both side constraints: $D$ violates the $a$ bound and $O$ the $b$ bound. The finite dual bound is therefore not evidence that the integer primal is feasible. The following part shows why this Lagrangian relaxation of an assignment with side constraints has a finite value anyway.

The assignment equalities parameterize every feasible matrix of the linear programming relaxation asThe side totals and objective becomeThe first side constraint gives $t\le 1/2$ and the second gives $t\ge 1/2$, so the relaxation has the unique feasible pointDirect elimination of the assignment equalities has solved this one-dimensional linear program. Its value matches the Lagrangian dual problem value because the retained assignment polytope is the convex hull of the two integer assignments; it does not make the side-constrained integer problem feasible.

With the new right sides, the dual function isTake $\lambda =\mu =t\to \infty$. Then ${\theta }_{\mathrm{new}}(t,t)=10-t\to -\infty$, so the minimization dual is unbounded below:By weak duality, any feasible integer point with finite objective would have to have objective at most every dual value, which is impossible. Thus the modified integer program is infeasible and has no optimal solution. This is an infeasibility certificate from an unbounded Lagrangian dual.

There is also a direct certificate: the assignment equalities force $(a+b)\cdot x=9$, while the new bounds force it to be at most $3+5=8$. Even the modified linear relaxation is infeasible. The earlier $3.5,5.5$ problem also had no integer solution, but there its fractional feasible point kept the dual value finite.

On a finite ground set $E$, a submodular rank function is a set function $r:2^E\to \mathbb{R}$ with the following properties:These are normalization, monotonicity, submodularity, and unit integer increments. In particular its values are nonnegative integers with $r(A)\le |A|$. Equivalently, one can require an integer-valued normalized monotone submodular function with $r(\{e\})\le 1$: diminishing returns then bounds every marginal increment by one. A general real-valued submodular function need not be a matroid rank.

Let item $j$ have weight $a_j$ and profit $p_j$. Define $D(j,b)$ as the largest profit obtainable from the first $j$ items with capacity at most the nonnegative integer $b$. Set $D(0,b)=0$. The last item is either absent or present once, giving the dynamic programming recursionThe two alternatives exhaust the feasible binary decisions. In the second alternative, deleting item $j$ leaves exactly the smaller subproblem with capacity $b-a_j$, which proves the recurrence.

Fill rows $j=1,\dots ,4$, and within each row capacities $b=0,\dots ,7$. Store which alternative attains each maximum. Backtrack from $(4,7)$: when exclusion was chosen, set $x_j=0$ and move to $(j-1,b)$; when inclusion was chosen, set $x_j=1$ and move to $(j-1,b-a_j)$. Ties may be resolved either way. Thus the stored values yield an actual optimal selection, not just its objective value.

For $n$ items and capacity $B$, the algorithm uses $O(nB)$ arithmetic operations and $O(nB)$ space with the full backtracking table. It is a pseudo-polynomial algorithm, since $B$ is a numerical capacity rather than its bit length. A value-only version can use one row, but must update capacities in decreasing order to avoid reusing the same item.

For each branch and bound node, relax the unfixed binary variables to $[0,1]$. The fractional knapsack problem is solved by decreasing profit-to-weight ratios, hereIts value is an upper bound for the node's integer optimum. At the root, greedy filling gives $x=(1,1,1/2,0)$ and upper bound $\boxed{43.5}$, so branch on $x_3$.

In the child $x_3=0$, the relaxed optimum is $(1,1,0,2/5)$ with value $43$. Branch on $x_4$. Taking $x_4=1$ leaves capacity two, giving the integral solution $(1,0,0,1)$ of value $40$, our incumbent. Taking $x_4=0$ gives the integral relaxed optimum $(1,1,0,0)$ of value $33$, so that node is closed.

In the child $x_3=1$, item four cannot be selected in any integer feasible solution, since their combined weight is nine. Fixing $x_4=0$ is therefore valid binary feasibility propagation. Its LP optimum is $(1,1/3,1,0)$ with value $42$. Branch on $x_2$. The child $x_2=1$ leaves no residual capacity and has integral solution $(0,1,1,0)$ of value $39$. The child $x_2=0$ has integral solution $(1,0,1,0)$ of value $36$. Both are below the incumbent.

The complete short search isAll integer feasible solutions lie in these branches, and every terminal node is integral with value at most forty. Therefore the LP bounds and incumbent certify $\boxed{z_{\mathrm{IP}}=40}$ independently of the dynamic program.

For each nonnegative integer $k$, the change of variables $x=e^{-t}$ givesThe gamma function identity $\Gamma (k+1)=k!$ follows by repeated integration by parts. Since $\log x<0$ on $(0,1)$, the sign of the original integrand is $(-1{)}^k$, soFor $k=0$, the integral is one, consistent with the formula.

The a.e. limit $f$ is nonnegative. For a fixed measurable set $A$, Fatou's lemma gives ${\int }_{A}f\le {\mathrm{liminf}}_n{\int }_A{f}_n$. Apply the same lemma to $A^c$ and use convergence of the total integrals:The lower and upper bounds prove $\boxed{{\int }_A{f}_n\to {\int }_{A}f}$.

For the asserted L1 convergence, choose an integer $k$ so large that ${\int }_{|x|>k}f<\epsilon$, possible by Lebesgue integrability. The first result applied to this fixed tail set makes ${\int }_{|x|>k}{f}_n<2\epsilon$ eventually. The additional local hypothesis makes ${\int }_{-k}^k|f_n-f|<\epsilon$ eventually. ThereforeThus $\boxed{\Vert f_n-f{\Vert }_{L^1(\mathbb{R})}\to 0}$.

In fact the extra local hypothesis is unnecessary here. Scheffé's lemma follows directly from $\min \{f_n,f\}\to f$ almost everywhere and domination by $f$:This stronger argument uses precisely the already assumed nonnegativity, a.e. convergence, and convergence of total integrals.