Friday, July 11, 2025

Proof of square tesselation with trominos

For each natural number n, consider a square consisting of 2^(2n) smaller squares (i.e., a 2^n × 2^n square). If any one of the smaller squares is removed from the large square (not necessarily from the corner), then the resulting region can be completely covered by trominos (each made up of three small squares of the same size as the small squares in the region) in such a way that the trominos do not overlap.

Yes, for every natural number n, if we remove any one of the 22n smaller squares from a 2n×2n square, it is always possible to tile the remaining region using only L-shaped trominos (three connected unit squares forming an "L") without overlap or gaps.


✅ Key Concepts:

  • A tromino is an L-shaped tile made up of 3 connected unit squares.
  • We are working with a 2n×2n square, which contains 22n unit squares.
  • One square is removed, leaving 22n1 unit squares to be tiled.

🧠 The Proof (by induction):

Base case: n=1

  • A 21×21=2×2 square has 4 unit squares.
  • Removing one square leaves 3 squares — which perfectly matches the shape of a tromino.
  • ✅ The base case holds.

Inductive step:

Assume the statement holds for some n=k: Any 2k×2k square with one square removed can be tiled with trominos.

Now consider a 2k+1×2k+1 square.

  • This square can be divided into four 2k×2k quadrants.
  • The removed square lies in one of these four quadrants.
  • By the inductive hypothesis, we can tile the affected quadrant after placing a tromino at the center of the full square that covers one square in each of the other three quadrants, near the center.
  • Now each of the four quadrants has one square missing, so each can be tiled by the inductive hypothesis.

✅ This completes the inductive step.


📌 Conclusion:

By mathematical induction, any 2n×2n square with one unit square removed can always be tiled completely with L-shaped trominos.


Would you like a visual demonstration or code to simulate this tiling?

Proof of Binet’s formula

Where x_n is the nth Fibonacci number, prove that nN,xn=15[(1+52)n(152)n].

To prove the closed‐form (“Binet’s”) formula

xn=15(ϕnψn),whereϕ=1+52,ψ=152,

we’ll show that the right‐hand side satisfies

  1. the same recurrence as the Fibonacci numbers,
  2. the same initial conditions,

and then invoke uniqueness of solutions to a linear recurrence.


1. Setup: characteristic equation

The Fibonacci numbers are defined by

x0=0,x1=1,xn=xn1+xn2(n2).

The associated characteristic polynomial is

r2r1=0,

whose two roots are

ϕ=1+52,ψ=152.

Since this is a distinct‐root second‐order homogeneous recurrence, its general solution is

an=Aϕn+Bψn

for constants A,B determined by a0 and a1.


2. Determine A and B via initial conditions

We want an=xn, so impose

  1. a0=A+B=x0=0,
  2. a1=Aϕ+Bψ=x1=1.

From A+B=0 we get B=A. Plugging into the second,

AϕAψ=1A(ϕψ)=1.

But ϕψ=5, so A=1/5 and hence B=1/5. Therefore

an=15ϕn15ψn=15(ϕnψn).


3. Check that an satisfies the Fibonacci recurrence

Since ϕ and ψ are roots of r2=r+1, we have

ϕn=ϕn1+ϕn2,ψn=ψn1+ψn2.

Hence

an=ϕnψn5=(ϕn1+ϕn2)(ψn1+ψn2)5=ϕn1ψn15+ϕn2ψn25=an1+an2.

Thus an obeys the same recurrence as xn.


4. Conclusion by uniqueness

We have produced a sequence an=(ϕnψn)/5 which

  • satisfies the same recurrence an=an1+an2,
  • has the same initial values a0=0, a1=1.

By the standard uniqueness theorem for linear recurrences, it follows that

an=xnnN.

That is,

xn=15(ϕnψn)=15((1+52)n(152)n).

This completes the proof. ∎

Primes using Fermat numbers

Define the nth Fermat number, Fn, by Fn=22n+1 for n = 0, 1, 2, 3, …. The first few Fermat numbers are F0 = 3, F1 = 5, F2 = 17, F3 = 257.

Prove by induction that F0 ⋅ F1⋯Fn-1 + 2 = Fn, for n ≥ 1.

Proof by induction on n1.


Base case (n=1)

We must check that

F0+2=F1.

Since F0=220+1=2+1=3 and F1=221+1=4+1=5, we have

F0+2=3+2=5=F1,

so the statement holds for n=1.


Inductive step

Inductive hypothesis. Suppose for some k1 that

F0F1Fk1+2=Fk.

Equivalently,

F0F1Fk1=Fk2.

We must show

F0F1Fk1Fk+2=Fk+1.

Starting from the left‐hand side,

F0F1Fk1Fk+2=(Fk2)Fk+2(by the inductive hypothesis).

Compute

(Fk2)Fk=Fk22Fk=(22k+1)22(22k+1).

Expand:

(22k+1)2=222k+222k+1=22k+1+22k+1+1,

so

Fk22Fk=(22k+1+22k+1+1)(22k+1+2)=22k+11.

Thus

F0F1Fk1Fk+2=(Fk22Fk)+2=(22k+11)+2=22k+1+1=Fk+1.

This completes the inductive step.


By the principle of mathematical induction, for every integer n1,

F0F1Fn1+2=Fn,

as claimed. ∎

Use this formula to prove that there are an infinite number of primes, by showing that no two Fermat numbers have any prime factors in common.

Here’s the standard argument.


1. Fermat numbers are pairwise coprime

Recall from the induction you’ve already proved that, for every n1,

Fn=F0F1Fn1+2.

Fix two indices 0m<n. Suppose p is a prime dividing both Fm and Fn. Then:

  1. Since pFn and

    Fn=F0F1Fn1+2,

    we have

    F0F1Fn1+20(modp)F0F1Fn12(modp).

  2. But pFm for some m<n, so p divides the product F0F1Fn1. Hence

    F0F1Fn10(modp).

  3. Combining the two congruences,

    0F0Fn12(modp)p2.

    Thus p=2. But every Fermat number Fk=22k+1 is odd, so cannot be divisible by 2.

Therefore no prime p can divide both Fm and Fn for m<n. Equivalently,

gcd(Fm,Fn)=1whenever mn.


2. Infinitely many primes

Since each Fermat number Fn is greater than 1, it has at least one prime divisor. By the argument above, no prime divisor of Fn can ever appear among the prime divisors of any other Fm with mn. Hence each Fn contributes at least one new prime that we have never seen before. As n ranges over the nonnegative integers, we thus get infinitely many distinct primes. ∎

Proof player 2 always wins by mirroring (Nim)

One version of a game called Nim is played as follows. There are two players and two piles consisting of the same natural number of objects; for this example, suppose the objects are nickels. At each turn, a player removes some number of nickels from either one of the piles. Then the other player removes some number of nickels from either of the piles. The players continue playing alternately until the last nickel is removed. The winner is the player who removes the last nickel.

Prove: If the second player always removes the same number of nickels that the first player last removed and does so from the other pile (thus making the piles equal in number after the second player’s turn), then the second player will win.

Here’s a clean “mirror”‐strategy proof that the second player (P₂) will always win.


Setup. – Two piles, each of size n. – Players alternate: P₁ goes first, then P₂, etc. – On your turn you remove any positive number of nickels from exactly one pile. – Whoever takes the very last nickel (i.e. empties the last nonempty pile) wins.


1. The Mirror Strategy

P₂’s rule. On each of P₁’s moves, say P₁ removes k nickels from one of the piles. Then P₂ immediately removes k nickels from the other pile.

Because the two piles were equal just before P₁’s move, removing k from one leaves one pile of size nk and the other still size n. Then P₂ can legally remove k from that size-n pile (since kn), restoring both piles to size nk.

Thus:

Invariant. At the end of each of P₂’s turns, the two piles are the same size.


2. Why This Guarantees a Win

  1. Base case (start of play). Before anyone moves, both piles are size n. So the invariant holds.

  2. Preservation. If at the end of one of P₂’s turns both piles are size m, then:

    1. P₁ removes k from one pile (with 1km), leaving piles (mk,m).
    2. P₂ then removes k from the other pile, leaving (mk,mk).
    3. Hence after P₂’s turn both piles are again the same size (mk).
  3. Termination & win. Eventually the piles shrink down. The first time P₁ empties a pile, say he takes all m remaining nickels from one pile, we have:

    After P₁’s move: piles (0,m).

    By the invariant m is exactly how many are in the “other” pile. P₂ then removes those last m nickels from that other pile—legally and wholly—leaving (0,0) and thus taking the very last coin.

Since P₂ never violates the rules (he always takes at most what’s available), and since this mirror‐move process ensures he makes the final removal, P₂ is guaranteed to win. ∎

Proof ∀n∈ℕ, n>1, ∀r∈ℝ\{1}, Σ(rᵏ)[k=0→(n-1)] = (rⁿ - 1)/(r-1)

Show that nN>1,rR{1},1+r+r2++rn1=rn1r1.

We are asked to prove the formula for the finite geometric series:

nN>1,rR{1},1+r+r2++rn1=rn1r1


Let’s define the left-hand side:

Let:

S=1+r+r2++rn1

This is a geometric series with:

  • First term a=1
  • Common ratio r
  • Number of terms n

We want to derive a closed-form expression for S.


Step 1: Multiply both sides by r

rS=r+r2+r3++rn


Step 2: Subtract the two equations

Subtract the original series S from rS:

rSS=(r+r2++rn)(1+r+r2++rn1)

Almost all terms cancel out:

rSS=rn1


Step 3: Factor out S

S(r1)=rn1


Step 4: Solve for S

Since r1, we can divide both sides:

S=rn1r1


Conclusion

Thus, we have shown that:

1+r+r2++rn1=rn1r1for all nN>1,rR{1}

✔️ Proven.

Proof ∀n>4, 2^n > n^2

Use induction to prove that ∀n>4, 2^n > n^2.

We want to prove by mathematical induction that:

n>4,2n>n2


Step 1: Base Case

Let n=5. We need to check whether the inequality holds:

25=32,52=25,and32>25

Base case holds.


Step 2: Inductive Hypothesis

Assume that the statement is true for some integer k5. That is, assume:

2k>k2

This is our inductive hypothesis.


Step 3: Inductive Step

We must show that this implies:

2k+1>(k+1)2

Start with:

2k+1=22k

Using the inductive hypothesis 2k>k2, we get:

2k+1=22k>2k2

So we want to show:

2k2>(k+1)2

Expand the right-hand side:

(k+1)2=k2+2k+1

So we want:

2k2>k2+2k+1

Subtract k2+2k+1 from both sides:

2k2(k2+2k+1)=k22k1>0

We now solve:

k22k1>0

Find the roots of k22k1=0:

k=2±4+42=2±82=2±222=1±2

So k22k1>0 for k>1+22.41

✅ Since we assume k5, the inequality holds.


Conclusion

By mathematical induction, we have shown that:

n>4,2n>n2

Proved.

Proof ∀n∈ℕ, 3^n > n^2

Show that, ∀n∈ℕ, 3^n > n^2.

We want to prove that

nN,3n>n2.


Step 1: Check small values of n

Let’s test a few small values to see when this inequality starts to hold:

  • n=1: 31=3>12=1
  • n=2: 32=9>22=4
  • n=3: 33=27>9
  • n=4: 34=81>16
  • n=5: 35=243>25

So far, 3n>n2 for all n=1,2,3,4,5. Now let’s prove this by induction.


Step 2: Mathematical Induction

Base Case: n=1

31=3>12=1✔️

Inductive Hypothesis:

Assume for some k1, the inequality holds:

3k>k2

Inductive Step: Show 3k+1>(k+1)2

Starting from the LHS:

3k+1=33k

Using the inductive hypothesis 3k>k2, we get:

3k+1=33k>3k2

So if we can show:

3k2>(k+1)2=k2+2k+1

then the inductive step will be complete.

Let’s prove that:

3k2>k2+2k+13k2(k2+2k+1)=2k22k1>0

Now check when 2k22k1>0. This is a quadratic in k. Solve:

2k22k1=0k=2±(2)2+84=2±124=2±234=1±32

So the inequality 2k22k1>0 holds when

k>1+321.366

Thus, for k2, the inequality is certainly true.


Step 3: Adjust the Domain

The inequality holds for all n1, and the inductive step is valid for k2. But:

  • Base cases n=1 and n=2: already checked and true.
  • Inductive step works from k=2 onward.

So we can conclude:


✅ Final Answer:

nN,n1,3n>n2

If you define N to include 0, then at n=0, 30=1>02=0, so it still holds. Thus:

nN,3n>n2