Skip over navigation
Cambridge University Faculty of Mathematics NRich logo
menu search
  • Teachers expand_more
    • Early years
    • Primary
    • Secondary
    • Post-16
    • Events
    • Professional development
  • Students expand_more
    • Primary
    • Secondary
    • Post-16
  • Parents expand_more
    • Early Years
    • Primary
    • Secondary
    • Post-16
  • Problem-Solving Schools
  • About NRICH expand_more
    • About us
    • Impact stories
    • Support us
    • Our funders
    • Contact us
  • search

Or search by topic

Number and algebra

  • The Number System and Place Value
  • Calculations and Numerical Methods
  • Fractions, Decimals, Percentages, Ratio and Proportion
  • Properties of Numbers
  • Patterns, Sequences and Structure
  • Algebraic expressions, equations and formulae
  • Coordinates, Functions and Graphs

Geometry and measure

  • Angles, Polygons, and Geometrical Proof
  • 3D Geometry, Shape and Space
  • Measuring and calculating with units
  • Transformations and constructions
  • Pythagoras and Trigonometry
  • Vectors and Matrices

Probability and statistics

  • Handling, Processing and Representing Data
  • Probability

Working mathematically

  • Thinking mathematically
  • Developing positive attitudes
  • Cross-curricular contexts

Advanced mathematics

  • Decision Mathematics and Combinatorics
  • Advanced Probability and Statistics
  • Mechanics
  • Calculus

For younger learners

  • Early Years Foundation Stage

Ordered Sums

Age 14 to 16
Challenge Level Yellow starYellow star
Secondary curriculum
  • Problem
  • Student Solutions

Let a(n) be the number of ways of expressing the integer n as an ordered sum of 1's and 2's. (For example a(4) = 5 because 4 = 2+2 = 2+1+1 = 1+2+1 = 1+1+2 = 1+1+1+1). Let b(n) be the number of ways of expressing n as an ordered sum of integers greater than 1; for example 4 can be written as 4 or as 2+2 so b(4) = 2. As another example, 5 can be written as 5 or as 2+3 or as 3+2 so b(5)=3.

The values of a(n) and b(n) for n < 9 are given in the following table. What do you notice about these sequences?

1 2 3 4 5 6 7 8 9
a(n) 1 2 3 5 8 13 21 34 55
b(n) 0 1 1 2 3 5 8 13 21

These are Fibonacci sequences and a(n) = b( n+2) for n >= 1.

The proof follows. To count the number of ways to write n as an ordered sum of 1's and 2's notice that any ordered sum must end in a 1 or a 2. If it ends in a 1 then there are a( n-1) ways of writing the previous terms and if it ends in a 2 then there are a( n-2) ways of forming these ordered sums. Hence the total number a(n) is given by a( n-1) + a( n-2). This is the recurrence relation for the Fibonacci sequence so a(n) is a `Fib'.

For b(n), that is for representations of n as sums of integers greater than 1, we first suppose the last term is k. Then we have:

n = * + * + ... + k (with k >= 2) (1)

If k=2 then the terms that come before have to add up to ( n-2) and so there are b( n-2) possible initial decompositions into ordered sums of integers.

If k>=3 then we subtract 1 in equation (1) to give:

n - 1 = * + * + ... + ( k-1) (with k-1 >=2) (2)

This has reduced the remaining representations to the conditions of the original definition, thus there are b( n-1) such representations. Hence b(n) = b( n-1) + b( n-2) giving the Fibonacci seqence.

As b(3) = 1 = a(1) and b(4) = a(2), where a(n) and b(n) satisfy the same recurrence relation when n>=2, it follows that b( n+2) = a(n) for n>=2.

You may also like

Doodles

Draw a 'doodle' - a closed intersecting curve drawn without taking pencil from paper. What can you prove about the intersections?

Russian Cubes

I want some cubes painted with three blue faces and three red faces. How many different cubes can be painted like that?

Polycircles

Show that for any triangle it is always possible to construct 3 touching circles with centres at the vertices. Is it possible to construct touching circles centred at the vertices of any polygon?

  • Tech help
  • Accessibility Statement
  • Sign up to our newsletter
  • Twitter X logo

The NRICH Project aims to enrich the mathematical experiences of all learners. To support this aim, members of the NRICH team work in a wide range of capacities, including providing professional development for teachers wishing to embed rich mathematical tasks into everyday classroom practice.

NRICH is part of the family of activities in the Millennium Mathematics Project.

University of Cambridge logo NRICH logo