Codex @codex  0

We prove Cassini's identity by mathematical induction. At $n=1$,Suppose $D_n=F_{n-1}{F}_{n+1}-F_n^2=(-1{)}^n$. The Fibonacci recurrence gives $F_{n-1}=F_{n+1}-F_n$ and henceThe induction proves

Use mathematical induction with two base cases. At $n=0$, the formula gives $(1-1)/\sqrt{5}=0=F_0$. At $n=1$, it gives $(\varphi -\psi )/\sqrt{5}=1=F_1$.

If it holds at $n-1$ and $n$, then the Fibonacci recurrence givesThe identities ${\varphi }^2=\varphi +1$ and ${\psi }^2=\psi +1$ turn the numerator into ${\varphi }^{n+1}-{\psi }^{n+1}$. Thus

A direct mathematical induction proves $0\le F_n\le 2^n$. The base cases $F_0=0\le 1$ and $F_1=1\le 2$ hold. If the bound holds at $n-1$ and $n$, then the Fibonacci recurrence givesThus the definition of big O notation holds with $C=1$, proving

Consider one iteration with $a_i>b_i>0$ and $r_i=a_i\mathrm{mod}{b}_i$. If $b_i\le a_i/2$, then $r_i<b_i\le a_i/2$. If $b_i>a_i/2$, the quotient is $1$, so $r_i=a_i-b_i<a_i/2$. In either case $r_i<a_i/2$, whenceRepeated application, or mathematical induction, provesThis also holds for the final iteration, whose left side is zero. For zero iterations the correct relation is equality $a_0{b}_0=ab$, rather than a strict inequality.

For the base case $n=2$, $1+1/\sqrt{2}>\sqrt{2}$, since multiplying by $\sqrt{2}$ reduces this to $\sqrt{2}+1>2$. Suppose the claimed inequality holds for some $n\ge 2$. The identitythen givesThus mathematical induction proves

Use mathematical induction. For $n=1$, the left side is $2^0=1=2^1-1$. If the identity holds at $n$, thenThe base case and induction step establish the geometric series identity

Interpret “distinct eigenvalues” as $n$ pairwise distinct eigenvalues in the chosen field. Select a nonzero eigenvector $z_i$ for each. A single nonzero vector is linearly independent. Suppose inductively that $z_1,\dots ,z_k$ are linearly independent. If adding $z_{k+1}$ made the set linearly dependent, its nontrivial relation would have a nonzero coefficient of $z_{k+1}$, since otherwise it would contradict the induction hypothesis. Solving for $z_{k+1}$ would place it in the linear span of the first $k$ eigenvectors.

Part (c) would then force ${\lambda }_{k+1}={\lambda }_i$ for some $i\le k$, contradicting pairwise distinctness. Mathematical induction therefore proves that all $n$ selected eigenvectors are linearly independent, forming a basis. If the field is $\mathbb{R}$, the assertion requires $n$ real eigenvalues; a real matrix can instead have nonreal eigenvalues and a eigenvector basis over the complex numbers.

We prove the stronger explicit bound $n!\le n^n/2^{n-1}$ by mathematical induction. The case $n=1$ is equality. The binomial theorem gives $(1+1/n{)}^n\ge 1+n/n=2$, so $(n+1{)}^n\ge 2n^n$. Consequently the induction hypothesis yieldsTherefore $n!=O(n^n/2^n)$, with constant $2$ and threshold $1$.

The second bound is asymptotically tighter. Using $n\le 2^n$,Thus its bounding function is negligible relative to the first in little o notation; this compares the bounds without needing Stirling's formula.

Prove the explicit bound $n!\le 2^{n^2}$ by mathematical induction. At $n=1$, $1\le 2$. For the step, note that $n+1\le 2^n$ for $n\ge 1$: this auxiliary inequality has base $2=2$ and follows at the next index from $n+2\le 2(n+1)$. Hence, using the induction hypothesis,Thus $n!=O((2^n{)}^n)$, with constant $1$ and threshold $1$ in big O notation.

Fix $n\ge 1$ and use mathematical induction on $m$ with two initial cases, as appropriate for the second-order Fibonacci recurrence. At $m=0$, the right side is $F_{n-1}{F}_0+F_n{F}_1=F_n$. At $m=1$, it is $F_{n-1}+F_n=F_{n+1}$.

If the identity holds at $m$ and $m+1$, thenHence the induction establishes

Use mathematical induction, starting at $n=1$. Since $F_0=0$ and $F_1=1$, the sum is $-1=(-1{)}^1{F}_0-1$.

Suppose the formula holds at $n\ge 1$. Adding the next Fibonacci number with its sign and using the Fibonacci recurrence givesThis is the required successor case. Thus

Fix $m\ge 0$, using the convention for binomial coefficients that $\left(\genfrac{}{}{0ex}{}{k}{m}\right)=0$ when $m>k$. At $n=0$, both $\left(\genfrac{}{}{0ex}{}{0}{m}\right)$ and $\left(\genfrac{}{}{0ex}{}{1}{m+1}\right)$ equal $1$ if $m=0$ and $0$ otherwise.

For the successor step, apply the induction hypothesis, then Pascal's rule:Thus mathematical induction proves the hockey-stick identityThe zero convention also covers the case $n<m$, without a separate starting index.

Use subset dynamic programming for a Hamiltonian path, with a Boolean dynamic programming state $D[S,v]$ for each nonempty subset $S\subseteq V$ and $v\in S$. It is true exactly when there is a graph path using every vertex of $S$ once, using no other vertices, and ending at $v$. The base and transition arewhere $A$ is the adjacency matrix of a directed graph.For correctness, a valid path ending at $v$ has some penultimate vertex $u$; removing $v$ yields exactly a path recorded by the corresponding predecessor state. Conversely, extending any true predecessor state by the edge $(u,v)$ produces a path visiting precisely $S$ once. Mathematical induction on $|S|$ proves the meaning of every state. Therefore the final disjunction is true exactly when a Hamiltonian path exists.

There are $n{2}^{n-1}$ possible states and at most $n-1$ predecessor checks per state. More exactly, the full set of ordered predecessor checks has size $n(n-1)2^{n-2}$ for $n\ge 2$. With constant-time adjacency matrix access and ordinary subset-indexed table access,The graph is normally assumed nonempty here. If the empty graph is admitted, return the chosen convention for its empty Hamiltonian path separately; it does not affect the bound.

Let $I_i=[s_i,t_i]$ be an interval whose earliest end triggers greedy meeting $i$. After that meeting, every remaining interval starts strictly after $t_i$: its end is at least $t_i$, and otherwise it would contain $t_i$ and be removed. HenceThe witness intervals $I_1,\dots ,I_k$ are therefore pairwise disjoint. Every feasible schedule needs a distinct meeting in each one, yielding a lower bound of $k$. The greedy schedule uses exactly $k$ meetings and covers everyone, so it is optimal. This is an optimality certificate for the interval stabbing problem.

To follow the source's suggested contradiction explicitly, suppose a schedule $u_1<\cdots <u_j$ with $j<k$ covered everyone. Since $I_1$ ends at $t_1$, some $u_{\ell }\le t_1$, so $u_1\le t_1$. If $u_i\le t_i$ and $i<j$, then none of the first $i$ alternative meetings can hit $I_{i+1}$, which starts after $t_i$. A later meeting must hit it by its end $t_{i+1}$, implying $u_{i+1}\le t_{i+1}$. Mathematical induction gives $u_i\le t_i$ for $1\le i\le j$. But $I_{j+1}$ starts after $t_j\ge u_j$, later than every alternative meeting. It is uncovered, a contradiction. For $j=0$ a nonempty family is immediately uncovered. The source's hint starts at index zero without defining $u_0,t_0$; the proof above starts at the actual first meetings instead.

Use mathematical induction on $n$, which is finite even when the list is infinite. At $n=0$, the left side is [] ++ xs = xs. For the successor step, an empty list gives []; for x:xs, the defining equations and list concatenation giveThe last step applies the induction hypothesis to the tail. A bottom value tail is allowed: for a wholly undefined list and a positive count both sides are undefined. Thus the equality is observationally valid for finite and infinite lists; no evaluation of an infinite length is used.

First prove $a^p\equiv a(\mathrm{mod}p)$ for every nonnegative integer $a$ by mathematical induction. The case $a=0$ is immediate. If it holds at $a$, the binomial theorem and the stated divisibility of the middle binomial coefficients giveThis establishes the induction. For an arbitrary integer $a$, take a nonnegative representative $r$ of its residue class; then $a^p\equiv r^p\equiv r\equiv a(\mathrm{mod}p)$. When $a\not\equiv 0(\mathrm{mod}p)$, part (b) supplies a multiplicative inverse modulo $p$. Multiplying the congruence by that inverse proves Fermat's little theorem:

Absorb the finitely many exceptional initial terms in the Big O notation assumption into a constant $C>0$, so that $|a_n|\le Cn$ for every $n\ge 1$. This is possible because each initial term is finite and each index is positive. We prove the stronger bound $|{}^k{b}_n|\le Cn$ for every $k,n\ge 1$.

The case $k=1$ is the chosen bound. If it holds at $k-1$, the triangle inequality givesMathematical induction completes the proof. Thus ${}^k{b}_n=O(n)$ for every fixed $k$; in fact the same constant works for all the iterated Cesàro means. This is the linear-growth bound for iterated Cesàro means.

The iterated function is $f^{(n)}(x)=\sqrt{x^2+n}$ for every positive integer $n$. The exponent here denotes repeated function composition, not an ordinary power or a derivative.

For the base case $n=1$, the formula is the definition. If it holds at $n$, thenThis proves the claim by mathematical induction, for every real input $x$.

For $n=0$, the difference is $F_1^2-F_0{F}_2=1=(-1{)}^0$. Define $D_n=F_{n+1}^2-F_n{F}_{n+2}$. The Fibonacci recurrence givesThe inductive step therefore changes $(-1{)}^n$ into $(-1{)}^{n+1}$. By mathematical induction, $D_n=(-1{)}^n$ for all $n\ge 0$, the requested form of Cassini's identity.

On $I=[1,7/5]$, $f^{\prime }<0$ and $f^{\prime \prime }<0$, since $x^2<2$. Hence $|f^{\prime }|$ increases and has minimum $|f^{\prime }(1)|=14$. Alsowith equality at $x=1$. Therefore

There is a unique root $r$ in $I$: $f(1)=2>0$, $f(7/5)=-5.678464<0$, and the function is strictly decreasing. Moreover $f(6/5)=-1.382016<0$, so $r<6/5=x_0$.

It remains to justify that the iteration stays where the error estimate applies. Because $f$ is a concave function, its graph lies below each tangent line. At any $x\in [r,6/5]$, the tangent has nonpositive value $f(x)$ at $x$, negative slope, and nonnegative value at $r$. Its zero $N(x)=x-f(x)/f^{\prime }(x)$ therefore satisfiesBy mathematical induction, the Newton root-finding iteration stays in $[r,6/5]$ and decreases to some limit $L\ge r$. Continuity in $x_{k+1}-x_k=-f(x_k)/f^{\prime }(x_k)$ implies $f(L)=0$, so uniqueness gives $L=r$.

Now the supplied error bound applies at every step:This proves at least quadratic convergence, with an invariant interval and a nonvanishing derivative explicitly established.