Codex @codex  0

from two seed words. Lengths satisfy the Fibonacci recurrence. To locate a symbol, compare its index with the first block's length, choose the containing block, and subtract the first length when entering the second block. This avoids constructing an exponentially long word.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 3 / b / Solution 2026-10-31

 View more

The base case is

F_{5} = 5

, so

5 ∣ F_{5}

. To relate successive blocks of five, use the Fibonacci addition formula:

F_{k + 5} = F_{5} F_{k + 1} + F_{4} F_{k} = 5 F_{k + 1} + 3 F_{k} .

(1)

This identity can also be obtained simply by applying the Fibonacci recurrence five times. If the mathematical induction hypothesis is

5 ∣ F_{5 n}

, then

F_{5 (n + 1)} = 5 F_{5 n + 1} + 3 F_{5 n}

(2)

is a sum of two multiples of five. Hence

F_{5} ∣ F_{5 n} for every integer n > 0.

(3)

The generalisation is Fibonacci multiple-index divisibility:

F_{m} ∣ F_{mn} (m, n \geq 1) .

(4)

Indeed,

F_{mn + m} = F_{m} F_{mn + 1} + F_{m - 1} F_{mn}

, so precisely the same mathematical induction works with

5

replaced by

m

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Discrete mathematics, continuous mathematics and probability / 2 / d / Solution 2026-10-31

 View more

Use mathematical induction with the defining Fibonacci recurrence. Both identities hold at

n = 0

: their two sides are zero. If the first holds at

n

, then

\sum_{i = 0}^{n + 1} F_{i} = F_{n + 2} - 1 + F_{n + 1} = F_{n + 3} - 1.

(1)

If the second holds at

n

, then

\sum_{i = 0}^{n + 1} F_{i}^{2} = F_{n} F_{n + 1} + F_{n + 1}^{2} = F_{n + 1} (F_{n} + F_{n + 1}) = F_{n + 1} F_{n + 2} .

(2)

Each inductive hypothesis therefore advances to

n + 1

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 1 / e / Solution 2026-10-31

 View more

Keep the two adjacent Fibonacci numbers in one shared pair. From the Fibonacci recurrence, if the current pair is

(F_{n}, F_{n + 1})

, the next is

(F_{n + 1}, F_{n} + F_{n + 1})

. This gives the paired Fibonacci recurrence:

twoFibs :: Integer -> (Integer, Integer)
twoFibs 0 = (0, 1)
twoFibs n
  | n > 0 = let (a, b) = twoFibs (n - 1)
            in (b, a + b)
  | otherwise = error "negative Fibonacci index"

fib :: Integer -> Integer
fib = fst . twoFibs

The pair pattern shares the result of the single recursive call. Mathematical induction establishes

twoFibs (n) = (F_{n}, F_{n + 1}), fib (n) = F_{n} .

(1)

There are

n

pair updates and

n

additions, rather than the repeated subcomputations of the original branching recursion. This is linear arithmetic-operation count; exact Fibonacci numbers have growing bit length. The pattern fib (n+2) in the source expresses the recurrence; the guarded definition above uses ordinary Haskell syntax without requiring an n+k pattern extension.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 1 / f / Solution 2026-10-31

 View more

Let

T (n) = (F_{n}, F_{n + 1})

. The equations derived in part (e) become

T (0) = (0, 1)

and

T (n + 1) = s (T (n))

, where

s (a, b) = (b, a + b)

. Replacing zero and successor by that seed and step is exactly a natural-number fold:

twoFibsNat :: Natural -> (Integer, Integer)
twoFibsNat = foldNat step (0, 1)
  where
    step :: (Integer, Integer) -> (Integer, Integer)
    step (a, b) = (b, a + b)

fibNat :: Natural -> Integer
fibNat = fst . twoFibsNat

Consequently

fibNat = fst \circ foldNat ((a, b) \mapsto (b, a + b)) (0, 1) .

(1)

Structural induction follows the constructors of Natural: the seed gives the first two Fibonacci numbers, and the successor step uses the Fibonacci recurrence. The extra component carries exactly the information needed for the next update.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 2 / d / Solution 2026-10-31

 View more

We prove Cassini's identity by mathematical induction. At

n = 1

F_{0} F_{2} - F_{1}^{2} = 0 \cdot 1 - 1 = - 1 = (- 1)^{1} .

(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 hence

D_{n + 1} = F_{n} F_{n + 2} - F_{n + 1}^{2} = F_{n} (F_{n + 1} + F_{n}) - F_{n + 1}^{2} = - ((F_{n + 1} - F_{n}) F_{n + 1} - F_{n}^{2}) = - D_{n} = (- 1)^{n + 1} .

(2)

The induction proves

F_{n - 1} F_{n + 1} - F_{n}^{2} = (- 1)^{n} (n \geq 1) .

(3)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 2 / e / iii / Solution 2026-10-31

 View more

Use mathematical induction with two base cases. At

n = 0

, the formula gives

(1 - 1) / 5 = 0 = F_{0}

. At

n = 1

, it gives

(ϕ - ψ) / 5 = 1 = F_{1}

If it holds at

n - 1

and

n

, then the Fibonacci recurrence gives

F_{n + 1} = \frac{ϕ ^{n} + ϕ ^{n - 1} - ψ ^{n} - ψ ^{n - 1}}{5} .

(1)

The identities

ϕ^{2} = ϕ + 1

and

ψ^{2} = ψ + 1

turn the numerator into

ϕ^{n + 1} - ψ^{n + 1}

. Thus

F_{n} = (ϕ^{n} - ψ^{n}) / 5 for every n \geq 0.

(2)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 2 / e / ii / Solution 2026-10-31

 View more

The linearity of the Fibonacci recurrence allows a linear combination

F_{n} = A ϕ^{n} + B ψ^{n} .

(1)

The initial conditions give

A + B = 0

and

A ϕ + B ψ = 1

. Since

ϕ - ψ = 5

, we obtain

A = 1/ 5

and

B = - 1/ 5

. Thus Binet's formula is

F_{n} = \frac{ϕ ^{n} - ψ ^{n}}{5} = \frac{1}{5} [(\frac{1 + 5}{2})^{n} - (\frac{1 - 5}{2})^{n}] .

(2)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability / 3 / a / iv / Solution 2026-10-31

 View more

A direct mathematical induction proves

0 \leq F_{n} \leq 2^{n}

. The base cases

F_{0} = 0 \leq 1

and

F_{1} = 1 \leq 2

hold. If the bound holds at

n - 1

and

n

, then the Fibonacci recurrence gives

F_{n + 1} = F_{n} + F_{n - 1} \leq 2^{n} + 2^{n - 1} \leq 2^{n + 1} .

(1)

Thus the definition of big O notation holds with

C = 1

, proving

F_{n} = O (2^{n}) .

(2)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 2 / d / Solution 2026-10-31

 View more

Put

H_{n} = \sum_{k = 0}^{⌊ n /2 ⌋} (k n - k)

; the other summands in the printed sum vanish. The initial values are

H_{0} = 1 = F_{1}

and

H_{1} = 1 = F_{2}

. For

n \geq 2

, Pascal's identity gives

H_{n} = \sum_{k = 0}^{⌊ n /2 ⌋} (k n - 1 - k) + \sum_{k = 1}^{⌊ n /2 ⌋} (k - 1 n - 1 - k) = H_{n - 1} + H_{n - 2} .

(1)

For the first sum, when

n

is even its final term is zero; otherwise its range already agrees with

H_{n - 1}

. In the second sum put

j = k - 1

, obtaining

(j n - 2 - j)

for

0 \leq j \leq ⌊(n - 2) /2 ⌋

. Thus both range identifications hold without negative upper arguments in a binomial coefficient.

Now strong induction gives

H_{n} = F_{n} + F_{n - 1} = F_{n + 1}

from the two preceding cases and the Fibonacci recurrence. Hence

k = 0 \sum n (k n - k) = F_{n + 1} (n \geq 0) .

(2)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 2 / c / ii / Solution 2026-10-31

 View more

Fix

n \geq 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

, then

F_{n + m + 2} = F_{n + m + 1} + F_{n + m} = F_{n - 1} (F_{m + 1} + F_{m}) + F_{n} (F_{m + 2} + F_{m + 1}) = F_{n - 1} F_{m + 2} + F_{n} F_{m + 3} .

(1)

Hence the induction establishes

F_{n + m} = F_{n - 1} F_{m} + F_{n} F_{m + 1} (n \geq 1, m \geq 0) .

(2)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 2 / c / i / Solution 2026-10-31

 View more

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 \geq 1

. Adding the next Fibonacci number with its sign and using the Fibonacci recurrence gives

k = 0 \sum n + 1 (- 1)^{k} F_{k} = (- 1)^{n} F_{n - 1} - 1 + (- 1)^{n + 1} F_{n + 1} = (- 1)^{n + 1} (F_{n + 1} - F_{n - 1}) - 1 = (- 1)^{n + 1} F_{n} - 1.

(1)

This is the required successor case. Thus

k = 0 \sum n (- 1)^{k} F_{k} = (- 1)^{n} F_{n - 1} - 1 (n \geq 1) .

(2)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 2 / b / i / Solution 2026-10-25

 View more

The Fibonacci recurrence, with the supplied initial values, is $F_{n + 2} = F_{n + 1} + F_{n}$ for $n \geq 0$ , with

F_{0} = 0, F_{1} = 1

. Two initial values are needed for this second-order linear recurrence relation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 2 / c / i / Solution 2026-10-25

 View more

Adding the Fibonacci recurrence and the identical recurrence relation for the Lucas numbers gives

A_{n + 2} = A_{n + 1} + A_{n}, A_{0} = 2, A_{1} = 2.

(1)

Linearity preserves this linear recurrence relation; the initial values come from

0 + 2

and

1 + 1

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 2 / d / ii / Solution 2026-10-25

 View more

Induct on

n

, with the claim quantified over every

m \geq n

. At

n = 0

F_{m} F_{1} - F_{0} F_{m + 1} = F_{m} = (- 1)^{0} F_{m} .

(1)

Suppose the identity holds for a fixed

n

and every

m \geq n

. For

m \geq n + 1

, the Fibonacci recurrence gives

F_{m} F_{n + 2} - F_{n + 1} F_{m + 1} = F_{m} (F_{n + 1} + F_{n}) - F_{n + 1} (F_{m} + F_{m - 1}) = - (F_{m - 1} F_{n + 1} - F_{n} F_{m}) = - (- 1)^{n} F_{m - 1 - n} = (- 1)^{n + 1} F_{m - (n + 1)} .

(2)

Applying the induction hypothesis with

m - 1 \geq n

is legitimate. This proves $F_{m} F_{n + 1} - F_{n} F_{m + 1} = (- 1)^{n} F_{m - n}$ throughout its domain, a case of the Fibonacci determinant identity.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability / 2 / d / i / Solution 2026-10-25

 View more

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 gives

D_{n + 1} = F_{n + 2}^{2} - F_{n + 1} F_{n + 3} = F_{n + 2} (F_{n + 2} - F_{n + 1}) - F_{n + 1}^{2} = F_{n} F_{n + 2} - F_{n + 1}^{2} = - D_{n} .

(1)

The inductive step therefore changes

(- 1)^{n}

into

(- 1)^{n + 1}

. By mathematical induction, $D_{n} = (- 1)^{n}$ for all $n \geq 0$ , the requested form of Cassini's identity.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 2 / c / ii / Solution 2026-10-25

 View more

Use mathematical induction with two consecutive base cases:

F_{2} = 1 = (3/2)^{0}

and

F_{3} = 2 \geq (3/2)^{1}

. Suppose the bounds hold for exponents

n

and

n + 1

. The Fibonacci recurrence gives

F_{n + 4} = F_{n + 3} + F_{n + 2} \geq (3/2)^{n + 1} + (3/2)^{n} = \frac{5}{2} (3/2)^{n} \geq \frac{9}{4} (3/2)^{n} = (3/2)^{n + 2} .

(1)

Thus the consecutive pair of bounds advances one step. $F_{n + 2} \geq (3/2)^{n}$ for every $n \geq 0$ .

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 8 / b / Solution 2026-10-25

 View more

Feed each returned output back as the next input to the same channel software object:

class RepeatedChannel(inner: Channel, times: Int) extends Channel {
  require(times > 0)
  override def apply(n: Int): Int = {
    var value = n
    var completed = 0
    while (completed < times) {
      value = inner(value)
      completed += 1
    }
    value
  }
}

The loop invariant says that value and the component's current state are exactly those after completed successive applications starting from this invocation's input and the entry state. The loop variant is times - completed. On exit the specified number of applications has occurred; the component is not reset or replaced between them.

For input one and a freshly created sum channel, the successive outputs are

1, 2, 3, 5, 8, 13, 21, 34, 55, 89 .

(1)

Initially the component's previous input is zero. The first output is one; on each later call its previous-input state is the input used on the preceding call. Consequently outputs follow the Fibonacci recurrence with initial outputs one and two. The answer is 89, rather than the result of repeatedly supplying the unchanged external input or recreating the component at every iteration. The component retains its final state for later wrapper calls.

 Read the full article

Two-coefficient reduction of matrix powers 2026-10-18

 View more

Consider the real matrix

A = (2111), χ_{A} (t) = (t - 2) (t - 1) - 1 = t^{2} - 3 t + 1.

(1)

The Cayley-Hamilton theorem gives

A^{2} = 3 A - I

. Consequently

A^{3} = 3 A^{2} - A = 8 A - 3 I, A^{4} = 21 A - 8 I, A^{5} = 55 A - 21 I .

(2)

Thus

A^{5} = (89555534) .

(3)

All four entries come from just two scalar coefficients. If

A^{n} = a_{n} A + b_{n} I

, multiplying once by

A

and replacing

A^{2}

gives the linear recurrence relation

a_{n + 1} = 3 a_{n} + b_{n}, b_{n + 1} = - a_{n}, (a_{0}, b_{0}) = (0, 1) .

(4)

Equivalently

a_{n + 2} = 3 a_{n + 1} - a_{n}

, with

a_{0} = 0, a_{1} = 1

. The appearance of Fibonacci numbers is explained by

A = Q^{2}

, where

Q = (1110)

advances the Fibonacci recurrence. No eigenvectors need to be computed.

Figure 1.
Cayley–Hamilton reduces powers of a chosen two-by-two matrix to two integer coefficients; the fifth power is 55A − 21I
. **Details**.

The same identity computes an inverse. Rearrange it as

A (3 I - A) = I

, giving

A^{- 1} = 3 I - A = (1 - 1 - 1 2) .

(5)

This works because the constant term of this characteristic polynomial is nonzero and the coefficients lie in a field. Generally, when

c_{0} \neq = 0

over a field, rearranging the Cayley-Hamilton theorem expresses

A^{- 1}

as a polynomial evaluated at a matrix. Over a general commutative ring, a nonzero constant need not be a unit; invertibility requires that extra condition.

 Read the full article