Strings

Deriving the Recurrence Let f(n) denote the count of valid binary strings of length n. Partition these strings by their last character: a(n): valid strings of length n ending in 0. b(n): valid strings of length n endi...

Updated May 21, 2026

Track IOI

Year 1989

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

Count the number of binary strings of length $n$ that contain no two consecutive 1s.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution

Deriving the Recurrence

Let $f(n)$ denote the count of valid binary strings of length $n$. Partition these strings by their last character:

$a(n)$: valid strings of length $n$ ending in 0.
$b(n)$: valid strings of length $n$ ending in 1.
Then $f(n) = a(n) + b(n)$, with recurrences:

\begin{align}a(n) &= a(n-1) + b(n-1), \\ b(n) &= a(n-1). \end{align}

The first equation holds because 0 can follow either ending. The second holds because 1 can only follow 0 (to avoid consecutive 1s).

Substituting: \[ f(n) = a(n) + b(n) = f(n-1) + a(n-1) = f(n-1) + f(n-2), \] where the last step uses $a(n-1) = a(n-2) + b(n-2) = f(n-2)$.

Theorem.

$f(n) = F_{n+2}$, where $F_k$ is the $k$-th Fibonacci number with $F_1 = F_2 = 1$.

Proof.

By induction. We have $f(1) = 2 = F_3$ and $f(2) = 3 = F_4$. For $n \ge 3$, $f(n) = f(n-1) + f(n-2) = F_{n+1} + F_n = F_{n+2}$.

Complexity Analysis

Time: $O(n)$ using iterative computation.
Space: $O(1)$, since only the two most recent values are needed.

Verification

$n$	$f(n)$	Valid strings
1	2	`0`, `1`
2	3	`00`, `01`, `10`
3	5	`000`, `001`, `010`, `100`, `101`
4	8	`0000`, `0001`, `0010`, `0100`, `0101`, `1000`, `1001`, `1010`
5	13	(Fibonacci pattern continues)

The sequence $2, 3, 5, 8, 13, 21, \ldots$ matches $F_3, F_4, F_5, \ldots$, confirming the formula.

Note on Overflow

For $n > 85$, the value of $f(n)$ exceeds the range of a 64-bit integer. If larger values of $n$ are needed, arbitrary-precision arithmetic (e.g., Python integers or a big-integer library) should be used.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 1989 - Problem 2: Strings
// Count binary strings of length n with no two consecutive 1s.
// Recurrence: f(n) = f(n-1) + f(n-2), f(1)=2, f(2)=3 (Fibonacci variant)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    if (n == 0) { printf("1\n"); return 0; }
    if (n == 1) { printf("2\n"); return 0; }

    long long prev2 = 2; // f(1)
    long long prev1 = 3; // f(2)
    for (int i = 3; i <= n; i++) {
        long long cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    printf("%lld\n", prev1);
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/1989/strings/solution.texC++ implementationcompetitive_programming/ioi/1989/strings/solution.cpp