Wednesday, July 23, 2025

Proof of Binet’s formula for the Fibonacci sequence

Briefly define the Fibonacci sequence.

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. It begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Mathematically, it's defined as:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) for n ≥ 2.

Prove that, ∀n∈ℕ, $F(n) = \frac {1}{\sqrt{5}} \left[\left(\frac {1 + \sqrt {5}}{2}\right)^n - \left(\frac {1 - \sqrt {5}}{2}\right)^n\right]$.

We are asked to prove Binet’s formula for the Fibonacci sequence:

$$ F(n) = \frac{1}{\sqrt{5}} \left[\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n\right], \quad \forall n \in \mathbb{N} $$


Step 1: Define the Fibonacci recurrence

The Fibonacci sequence is defined as:

  • $F(0) = 0$
  • $F(1) = 1$
  • $F(n) = F(n-1) + F(n-2)$, for $n \geq 2$

Step 2: Use recurrence relation approach with characteristic equation

Assume a solution of the form:

$$ F(n) = A\alpha^n + B\beta^n $$

where $\alpha$ and $\beta$ are the roots of the characteristic equation derived from the recurrence:

$$ x^2 = x + 1 \Rightarrow x^2 - x - 1 = 0 $$

Solving this quadratic:

$$ \alpha = \frac{1 + \sqrt{5}}{2}, \quad \beta = \frac{1 - \sqrt{5}}{2} $$

So the general solution becomes:

$$ F(n) = A\alpha^n + B\beta^n $$


Step 3: Solve for constants $A$ and $B$

Using initial conditions:

For $n = 0$:

$$ F(0) = A\alpha^0 + B\beta^0 = A + B = 0 \Rightarrow B = -A $$

For $n = 1$:

$$ F(1) = A\alpha + B\beta = A\alpha - A\beta = A(\alpha - \beta) = 1 $$

We calculate $\alpha - \beta$:

$$ \alpha - \beta = \frac{1 + \sqrt{5}}{2} - \frac{1 - \sqrt{5}}{2} = \frac{2\sqrt{5}}{2} = \sqrt{5} $$

So:

$$ A(\sqrt{5}) = 1 \Rightarrow A = \frac{1}{\sqrt{5}}, \quad B = -\frac{1}{\sqrt{5}} $$


Step 4: Final formula

Substitute $A$ and $B$ back into the general solution:

$$ F(n) = \frac{1}{\sqrt{5}} \alpha^n - \frac{1}{\sqrt{5}} \beta^n = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n \right) $$


✅ Conclusion

We have proven that:

$$ \boxed{F(n) = \frac {1}{\sqrt{5}} \left[\left(\frac {1 + \sqrt {5}}{2}\right)^n - \left(\frac {1 - \sqrt {5}}{2}\right)^n\right]} $$

holds for all $n \in \mathbb{N}$.

Monday, July 21, 2025

Natural language formal grammars

Nowadays what's the most advanced fully formalized formal grammar for a natural language?

Short answer : For a single natural language, the English Resource Grammar (ERG)—currently at its May 2025 release—is generally regarded as the most advanced, fully formalised grammar that actually runs on a computer. It is hand-built in the HPSG formalism, covers 90-plus % of open-domain English, and produces logic-ready Minimal Recursion Semantics (MRS) representations. (Delph-in)


Why the ERG stands out

Aspect What the ERG offers
Theoretical foundation Head-Driven Phrase-Structure Grammar with a rich type hierarchy of 1 100+ lexical/phrased-structure types
Coverage & precision ~35 000 lexemes, ~200 syntactic rules; parses ≈ 94 % of Wall-Street-Journal sentences and > 90 % of contemporary web text while staying linguistically faithful (iafisher.com)
Semantics Direct compositional output in MRS, compatible with downstream inference, QA, RTE and MT pipelines (Delph-in)
Tool chain Ships as a binary grammar (“erg-2025-x86-64-0.9.34.dat”) for the ACE parser and for LKB/pyDelphin; also accessible through a REST API (Delph-in)
Sustained maintenance Active DELPH-IN community, annual releases; latest tagged 2025

Because every rule, feature structure and semantic predicate is machine-checkable, ERG is what linguists call a precision grammar: if it accepts a sentence, it guarantees an internally consistent syntactic and semantic analysis. That property makes it the go-to resource for deep NLP experiments and for testing linguistic hypotheses.


How does it compare to other large formal grammars?

Project Formalism Languages Maturity & scope
ParGram / XLE grammars Lexical-Functional Grammar (LFG) ≈ 10 major languages (EN, FR, DE, JA…) High-quality parallel grammars but smaller coverage per language; used mainly in grammar-checking research (iafisher.com)
GF Resource Grammar Library (RGL) Type-theoretical GF 45 + languages Elegant multilingual framework for generation & controlled NL; not yet as deep or wide-coverage per language as ERG (grammaticalframework.org)
OpenCCG / CCGBank grammar Combinatory Categorial Grammar English Grammar induced from CCGBank; broad but automatically derived, with less hand-verified precision than ERG (GitHub)
Resource Grammars (Jacy, SRG, etc.) HPSG Japanese, Spanish, Norwegian… Built with the same methodology as ERG; none yet match ERG’s size or stability (e.g. Spanish RG revival 2024)

In short, those projects show that formalised, executable grammars are feasible for many languages, but the ERG remains the flagship in terms of depth, breadth, and semantic integration.


Take-away

If you need a fully formal, broad-coverage, linguistically rigorous grammar that you can parse and generate with today, the ERG is the state of the art. For cross-lingual work, look toward the GF RGL or the ParGram LFG suite, but be prepared for more limited coverage or weaker semantic output.

Division Algorithm for Polynomials

Prove this: Let f(x), g(x) be two polynomials with deg(f) ≤ deg(g). Then there are unique polynomials q(x), r(x) such that g(x) = q(x)f(x) + r(x), where deg(r) < deg(f).

Proof (Division Algorithm for Polynomials)

Let $f(x)$ and $g(x)$ be polynomials over a field (or integral domain) $K$, with

$$ \deg(f) \le \deg(g). $$

We will show:

  1. Existence: there exist polynomials $q(x)$ and $r(x)$ such that

    $$ g(x) = q(x)\,f(x) + r(x), $$

    with $\deg(r)<\deg(f)$.

  2. Uniqueness: this representation is unique.


1. Existence

We proceed by induction on $n = \deg(g)$.

  • Base case: If $\deg(g) < \deg(f)$, then we may simply take

    $$ q(x) = 0, \qquad r(x) = g(x). $$

    Clearly $g = 0\cdot f + g$, and $\deg(r)=\deg(g)<\deg(f)$.

  • Inductive step: Suppose the statement holds for all polynomials of degree less than $n$, and let $\deg(g)=n\ge\deg(f)$. Write

    $$ f(x) = a_m x^m + \dots,\quad g(x)=b_n x^n + \dots $$

    with $a_m,b_n\neq0$. Since $n\ge m$, set

    $$ t(x) \;=\;\frac{b_n}{a_m}\,x^{n-m}. $$

    Then $\deg\bigl(t(x)\,f(x)\bigr)=n$, and its leading coefficient matches that of $g(x)$. Consider

    $$ g_1(x) \;=\; g(x)\;-\;t(x)\,f(x). $$

    By construction, $\deg(g_1)<n$. Now by the induction hypothesis applied to $g_1$ (whose degree is $<n$), there exist polynomials $q_1(x)$ and $r(x)$ with

    $$ g_1(x) = q_1(x)\,f(x) + r(x), \qquad \deg(r)<\deg(f). $$

    Hence

    $$ g(x) = t(x)\,f(x) + g_1(x) = t(x)\,f(x) + \bigl(q_1(x)\,f(x) + r(x)\bigr) = \bigl(t(x)+q_1(x)\bigr)\,f(x) + r(x). $$

    Setting $q(x)=t(x)+q_1(x)$ gives the desired representation for $g$, with $\deg(r)<\deg(f)$.

By induction, such $q(x)$ and $r(x)$ always exist.


2. Uniqueness

Suppose there are two representations

$$ g(x) = q_1(x)\,f(x) + r_1(x), \qquad g(x) = q_2(x)\,f(x) + r_2(x), $$

with $\deg(r_1),\deg(r_2)<\deg(f)$. Subtracting gives

$$ 0 = \bigl(q_1(x)-q_2(x)\bigr)\,f(x)\;+\;\bigl(r_1(x)-r_2(x)\bigr). $$

Rearrange:

$$ \bigl(q_1(x)-q_2(x)\bigr)\,f(x) = -\bigl(r_1(x)-r_2(x)\bigr). $$

  • The left side is a multiple of $f(x)$, so if $q_1\neq q_2$ then $\deg\bigl((q_1-q_2)f\bigr)\ge \deg(f)$.
  • The right side is $r_2(x)-r_1(x)$, whose degree is strictly less than $\deg(f)$.

The only way a nonzero polynomial of degree $\ge\deg(f)$ can equal one of degree $<\deg(f)$ is if both are the zero polynomial. Hence

$$ q_1(x)-q_2(x) \;=\; 0, \quad r_1(x)-r_2(x)\;=\;0, $$

so $q_1 = q_2$ and $r_1 = r_2$. This proves uniqueness.


Together, these two parts establish the Division Algorithm for polynomials: for any $f(x)$ and $g(x)$ with $\deg(f)\le\deg(g)$, there exist unique polynomials $q(x)$ and $r(x)$ such that

$$ g(x) = q(x)\,f(x) + r(x), \quad \deg(r)<\deg(f). $$

$\quad\blacksquare$

Motivation for decomposition into even and odd functions

Every function can be expressed uniquely as the sum of an even function and an odd function, like so: let E(x) be (f(x)+f(-x))/2, and let O(x) be (f(x)-f(-x))/2. Then E(x) is even, O(x) is odd, and f(x) = E(x) + O(x).

But what’s the point of doing this?

Decomposing any function $f$ into its even and odd parts

$$ E(x) = \frac{f(x)+f(-x)}2,\quad O(x)=\frac{f(x)-f(-x)}2,\quad f=E+O $$

is more than just a neat algebraic trick. Here’s why it’s so useful:


1. Exploiting symmetry in integrals

  • Odd integrals vanish: if $O$ is odd, then

    $$ \int_{-a}^a O(x)\,dx = 0. $$

    So

    $$ \int_{-a}^a f(x)\,dx = \int_{-a}^a E(x)\,dx + \underbrace{\int_{-a}^a O(x)\,dx}_{0} = 2\int_0^a E(x)\,dx. $$

    You’ve halved your work by reducing to the even part only.


2. Fourier series simplification

  • An arbitrary periodic $f$ has a Fourier series

    $$ f(x)=a_0 + \sum_{n=1}^\infty\bigl[a_n\cos(nx)+b_n\sin(nx)\bigr]. $$

  • The cosine terms are the even part; the sine terms are the odd part.

  • You can immediately tell which coefficients vanish if you know $f$ is purely even or purely odd.


3. Power-series (Taylor) clarity

  • Expanding about zero, an even function has only even powers:

    $$ E(x)=c_0 + c_2 x^2 + c_4 x^4 + \cdots, $$

    while an odd function has only odd powers:

    $$ O(x)=c_1 x + c_3 x^3 + \cdots. $$

  • Decomposition helps identify which terms must be present or zero in your series.


4. Solving differential equations

  • Many differential operators commute with the “flip” $x\mapsto -x$, so they preserve evenness/oddness.
  • You can split a boundary-value or initial-value problem into two simpler problems—one on the even subspace, one on the odd—often halving the complexity.

5. Linear-algebra viewpoint

  • The space of all functions (say, on $\mathbb{R}$) decomposes as

    $$ \{\,\text{even}\}\ \oplus\ \{\text{odd}\}. $$

  • Projection onto each subspace is exactly $E$ and $O$. This is a concrete example of projecting onto complementary subspaces in any vector space.


6. Practical computations & modeling

  • In physics and engineering, boundary conditions often enforce symmetry. If you know a solution must be even (or odd), you can discard half the domain or simplify the ansatz immediately.
  • In signal processing, even/odd decomposition relates to splitting a signal into its symmetric and antisymmetric components, each of which may carry different information.

In short

Breaking $f$ into $E+O$ lets you

  1. Harness symmetry to simplify integrals and equations.
  2. Organize expansions (Fourier, Taylor) by parity.
  3. Project cleanly onto invariant subspaces.

It’s a fundamental tool whenever symmetry—or the lack of it—can be used to your advantage.

Completeness of isohedral figure classification

The table below was simplified from the table at this Wikipedia article.

Here is a table of isohedral figures from Wikipedia. Is it proven that all isohedral figures must be one of these things – a Platonic solid, a Catalan solid, or one of these pyramid-stacking “polar” figures?

Faces Face config. Class Name Symmetry Order
4 V33 Platonic tetrahedron Td, [3,3], (*332) 24
4 V33 Platonic tetragonal disphenoid D2d, [2+,2], (2*) 4
4 V33 Platonic rhombic disphenoid D2, [2,2]+, (222) 4
6 V34 Platonic cube Oh, [4,3], (*432) 48
6 V34 Platonic cube D3d, [2+,6] 12
6 V34 Platonic cube (2*3) 12
6 V34 Platonic trigonal trapezohedron D3 6
6 V34 Platonic asymmetric trigonal trapezohedron [2,3]+, (223) 6
8 V43 Platonic octahedron Oh, [4,3], (*432) 48
8 V43 Platonic octahedron D4h,[2,4],(*224) 16
8 V43 Platonic octahedron D2h,[2,2],(*222) 8
8 V43 Platonic square bipyramid D2d,[2+,4],(2*2) 8
8 V43 Platonic rhombic bipyramid D2d,[2+,4],(2*2) 8
8 V43 Platonic square scalenohedron D2d,[2+,4],(2*2) 8
12 V35 Platonic regular dodecahedron Ih, [5,3], (*532) 120
12 V35 Platonic regular dodecahedron Th, [3+,4], (3*2) 24
12 V35 Platonic regular dodecahedron T, [3,3]+, (*332) 12
12 V35 Platonic pyritohedron T, [3,3]+, (*332) 12
12 V35 Platonic tetartoid T, [3,3]+, (*332) 12
20 V53 Platonic regular icosahedron Ih, [5,3], (*532) 120
12 V3.62 Catalan triakis tetrahedron Td, [3,3], (*332) 24
12 V(3.4)2 Catalan rhombic dodecahedron Oh, [4,3], (*432) 48
12 V(3.4)2 Catalan rhombic dodecahedron Td, [3,3], (*332) 24
12 V(3.4)2 Catalan deltoidal dodecahedron Td, [3,3], (*332) 24
24 V3.82 Catalan triakis octahedron Oh, [4,3], (*432) 48
24 V4.62 Catalan tetrakis hexahedron Oh, [4,3], (*432) 48
24 V3.43 Catalan deltoidal icositetrahedron Oh, [4,3], (*432) 48
48 V4.6.8 Catalan disdyakis dodecahedron Oh, [4,3], (*432) 48
24 V34.4 Catalan pentagonal icositetrahedron O, [4,3]+, (432) 24
30 V(3.5)2 Catalan rhombic triacontahedron Ih, [5,3], (*532) 120
60 V3.102 Catalan triakis icosahedron Ih, [5,3], (*532) 120
60 V5.62 Catalan pentakis dodecahedron Ih, [5,3], (*532) 120
60 V3.4.5.4 Catalan deltoidal hexecontahedron Ih, [5,3], (*532) 120
120 V4.6.10 Catalan disdyakis triacontahedron Ih, [5,3], (*532) 120
60 V34.5 Catalan pentagonal hexecontahedron I, [5,3]+, (532) 60
2n V33.n Polar trapezohedron Dnd, [2+,2n], (2*n) 4n
2n V33.n Polar trapezohedron Dn, [2,n]+, (22n) 2n
2n V33.n Polar asymmetric trapezohedron Dn, [2,n]+, (22n) 2n
2n V42.n Polar regular n-bipyramid Dnh, [2,n], (*22n) 4n
2n V42.2n Polar isotoxal 2n-bipyramid Dnh, [2,n], (*22n) 4n
2n V42.2n Polar 2n-scalenohedron Dnd, [2+,2n], (2*n) 4n
4n V42.2n Polar 2n-scalenohedron Dnd, [2+,2n], (2*n) 4n

Short answer

Yes – for convex polyhedra the classification is finished. Branko Grünbaum and Geoffrey C. Shephard completed it in their study of isohedral (face-transitive) tilings of the sphere, and the result is exactly what your table shows:

  • 5 Platonic solids

  • 13 Catalan solids (duals of the Archimedean solids)

  • Three infinite polar families

    • the (general) scalenohedra / isosceles tetrahedra
    • the $n$-bipyramids (duals of prisms)
    • the $n$-trapezohedra (duals of antiprisms)

Together these make up 30 “classes’’: 28 individual solids and 2 one-parameter families whose face-count grows with $n$. MathWorld’s Isohedron page quotes the same total and traces it to the Grünbaum–Shephard work (MathWorld), while Wikipedia summarises the duality-based reasoning – Platonic ↔ Platonic, Archimedean → Catalan, prism → bipyramid, antiprism → trapezohedron (Wikipedia).

What the proof looks like (in outline)

  1. Work on the sphere. Any convex polyhedron gives a tiling of the unit sphere by projecting its faces outward.

  2. Classify all face-transitive spherical tilings. Grünbaum & Shephard (1981) listed every way a single tile can repeat around the sphere under a finite symmetry group.

  3. Lift the tilings back to space. Each tiling corresponds to either

    • a Platonic solid,
    • the dual of a uniform spherical tiling (hence a Catalan solid), or
    • a 2-cap tiling whose dual is a bipyramid or trapezohedron. No other convex embedding exists – that’s the heart of the proof.

Because the argument happens on the sphere, it automatically rules out any stray convex isohedra that look different but would project to one of the known patterns.

Limits of the result

  • If you drop convexity (allow self-intersection or star faces) there are many more isohedra, starting with the four Kepler–Poinsot polyhedra, and no complete list is known.
  • If you go up one dimension (4-polytopes) or down to tilings of the plane, the problem is again open.
  • Even in 3-D, the weaker “all faces merely congruent’’ condition (monohedral) is not classified; several sporadic convex examples are known that are not isohedral (Mathematics Stack Exchange).

So, within the usual confines of convex solids the answer is yes – every isohedron is either Platonic, Catalan, or one of the polar stack-of-pyramids families on your list. Outside that safe zone, the zoo is still very much alive and un-catalogued.

Do you have the citation for the study by Branko Grünbaum and Geoffrey C. Shephard?

Below is the full bibliographic information that most authors cite when they refer to the Grünbaum–Shephard classification of isohedral (face-transitive) spherical tilings—which, in turn, yields the list of convex isohedral polyhedra you asked about.

Ref. Standard citation (APA-style) Notes
[GS 1981a] Grünbaum, B., & Shephard, G. C. (1981). Spherical tilings with transitivity properties. In C. Davis, B. Grünbaum & F. A. Sherk (Eds.), The Geometric Vein: The Coxeter Festschrift (pp. 65-98). Springer-Verlag. https://doi.org/10.1007/978-1-4612-5648-9_4 The definitive, worked-out classification of all isohedral, isotoxal and isogonal tilings of the 2-sphere. Convex isohedral polyhedra correspond to these tilings via radial projection and duality. (SpringerLink)
[GS 1981b] Grünbaum, B., & Shephard, G. C. (1981). Patterns on the 2-sphere. Mathematika, 28(1), 1-35. https://doi.org/10.1112/S0025579300015321 A shorter companion journal article that previews some of the same results in a more compressed form. (londmathsoc.onlinelibrary.wiley.com)

Either reference is usually accepted; the book chapter [GS 1981a] is the most frequently quoted source when people assert that “every convex isohedron is Platonic, Catalan, or one of the three polar families.”

Thursday, July 17, 2025

To The Winner Go The Potatoes

In the philosophy of Humanitism, what does it mean that "to the winner go the potatoes"?

Short answer: In Machado de Assis’s satirical “philosophy” of Humanitism (Portuguese Humanitismo), the slogan “Ao vencido, ódio ou compaixão; ao vencedor, as batatas” (“To the vanquished, hatred or pity; to the victor, the potatoes”) sums up Quincas Borba’s claim that in any struggle for scarce resources the side that prevails rightfully takes the means of survival—the potatoes—while the losers’ fate doesn’t matter because individual lives are insignificant next to the abstract totality “Humanitas.” It’s a darkly comic reduction of grand metaphysics to crude material spoils, used by Machado to parody Social-Darwinist and positivist justifications for violence, competition, and social inequality. (Wikisource, Scribd, Wikipedia)


How the motto is introduced

Quincas Borba explains to Rubião: imagine a field with potatoes enough to nourish only one of two starving tribes; if they share, both die; if one destroys the other, the survivors gain strength to reach more food. Hence “peace is destruction; war is preservation… To the vanquished, hatred or compassion; to the victor, the potatoes.” (Wikisource, Scribd, TeX talk)

What it asserts within Humanitism

From this parable Borba infers that conflict which secures resources for the stronger side serves life and thus serves the universal substance Humanitas; individuals are mere “bubbles” in the boiling water—transient phenomena whose extinction is irrelevant to the underlying whole. The ethical upshot: material benefit to the winner trumps concern for the defeated. (Wikisource, Scribd, Wikipedia, biblioteca.pucrs.br)

Machado’s satirical target

Critics read Humanitism as Machado’s parody of nineteenth-century scientistic creeds—especially Social Darwinism and Comtean positivism—that dressed up the “law of the strongest” in lofty philosophical language. By pushing this logic to absurdity (“to the winner, the potatoes”), Machado exposes the inhuman, self-justifying moral calculus that can underwrite war, exploitation, or simple greed. (Wikipedia, TeX talk, lac.ox.ac.uk, Terra)

Later and idiomatic use

Because the scene is so memorable, “Ao vencedor, as batatas” has entered Brazilian Portuguese as an idiom roughly equivalent to “to the victor go the spoils,” invoked—often wryly—in contexts of competition, money, or power to mean that the winner walks away with the goods. (Wiktionary, Terra, VEJA, biblioteca.pucrs.br)


In sum: Within Humanitism the phrase literalizes a brutal survival calculus (winner eats; loser disappears) and, by exaggeration, lets Machado de Assis mock any philosophy that rationalizes inequality or violence as serving some higher good. (Wikisource, Scribd, Wikipedia)

Proof ∀a,b ∈ ℝ [ a = b ⇔ ( ∀ ϵ ∈ ℝ [ ϵ > 0 ⇒ |a − b| < ϵ ] ) ]

Prove ∀a,b ∈ ℝ [ a = b ⇔ ( ∀ ϵ ∈ ℝ [ ϵ > 0 ⇒ |a − b| < ϵ ] ) ].

We are asked to prove the equivalence:

$$ \forall a,b \in \mathbb{R},\quad a = b \iff \left( \forall \epsilon \in \mathbb{R},\ \epsilon > 0 \Rightarrow |a - b| < \epsilon \right) $$

We will prove this biconditional statement by proving both directions:


(⇒) Forward direction:

Assume $a = b$. We want to show:

$$ \forall \epsilon > 0,\ |a - b| < \epsilon $$

Since $a = b$, we have $|a - b| = |0| = 0$. For any $\epsilon > 0$, clearly $0 < \epsilon$. So, $|a - b| < \epsilon$.

✅ Thus, the implication holds in the forward direction.


(⇐) Reverse direction:

Assume:

$$ \forall \epsilon > 0,\ |a - b| < \epsilon $$

We want to show $a = b$. We’ll proceed by contradiction:

Suppose $a \ne b$. Then $|a - b| = \delta$ for some $\delta > 0$. Now, choose $\epsilon = \delta/2 > 0$. Then:

$$ |a - b| = \delta > \delta/2 = \epsilon $$

This contradicts the assumption that $|a - b| < \epsilon$ for all $\epsilon > 0$.

❌ So, the assumption $a \ne b$ must be false. Hence:

✅ $a = b$


Conclusion:

$$ \boxed{ \forall a,b \in \mathbb{R},\quad a = b \iff \forall \epsilon > 0,\ |a - b| < \epsilon } $$