C++ examples: Sequences

This material is on sequences defined by induction, where previous numbers in the sequence are used to define new numbers in the sequence. It will give you the opportunity to code in the C++ style, and use loops and variables in your C++ program.

1. Some sequences

Definition.

One related to $φ$ (the so-called Golden Section) is the sequence $(φ_{n})$ where $φ_{0} = 1$ , and $φ_{n + 1} = 1 + (1 / φ_{n})$ .

Obviously, if you know $φ_{n}$ that is enough to calculate $φ_{n + 1}$ . Therefore knowing $φ_{0} = 1$ is going to be enough to calculate the whole sequence. What's more, we can do this with a computer program and a fixed number of variables since we never have to remember more than the last value.

Definition.

A similar looking sequence is $(χ_{n})$ where $χ_{0} = 1$ , and

χ_{n + 1} = 1 + \frac{1}{1 + χ_{n}}

Definition.

If we use a constant $α$ the two preceding sequences can be combined into one definition $(ψ_{n})$ where $ψ_{0} = 1$ , and

ψ_{n + 1} = 1 + \frac{1}{α + ψ_{n}}

Note that $φ_{n}$ is $ψ_{n}$ where $α = 0$ and $χ_{n}$ is $ψ_{n}$ where $α = 1$ .

Definition.

Another interesting sequence is defined using a constant $β$ . Define $(c_{n})$ by $c_{0} = 1$ , $c_{1} = β$ , and $c_{n + 1} = 2 β c_{n} - c_{n - 1}$ .

The case of the $c_{n}$ sequence is similar. It can be calculated by remembering $β$ and the two last values.

Here is a C++ program to calculate values of $c_{n}$ .

#include <iostream>
using namespace std;

int main() {

  // an example value for the parameter beta
  double beta = 0.8660254037844386467637;

  int maxn;  
  cout << "maximum index? ";
  cin >> maxn;

  double c = 0;              // current value
  double c_prev = beta;      // previous value
  double c_prev_prev = 1.0;  // one before that

  cout << "c_0" << " == " << c_prev_prev << endl;
  cout << "c_1" << " == " << c_prev << endl;
  int n = 1;
  while (n < maxn) {
    n = n + 1;
    c = 2*beta*c_prev - c_prev_prev;
    cout << "c_" << n << " == " << c << endl;
    c_prev_prev = c_prev;
    c_prev = c;
  }

  return 0;
}

You can copy it and compile it. The value used here for beta is $\sqrt{3} / 2$ which is (to sufficiently high accuracy) about 0.8660254037844386467637. You can try other values of $β$ such as 0, 1, 0.5, but values between -1 and +1 might be best. (But why? try others too.)

Exercise.

(Possibly tricky, unless you spot a good idea.) Can you give an expression for the value $c_{n}$ for a given value $β$ in the range from $-1$ to $+1$ ?

Exercise.

Program the $(ψ_{n})$ sequence in the same way.

Exercise.

Do the sequences $(φ_{n})$ and/or $(χ_{n})$ converge? If so, to what?

Note: you can if you want change the program to accept a value beta (or alpha) from the user when the program is run. For example,

  double beta = 1;
  cout << "Please give value for beta: " ;
  cin >> beta;

2. The Fibonacci numbers and some variants

Definition.

The Fibonacci numbers are defined as the real numbers $f_{n}$ where $f_{0} = 0$ , $f_{1} = 1$ and $f_{n + 1} = f_{n - 1} + f_{n}$ for all $n ⩾ 1$ .

So according to this definition the Fibonacci number with subscript $2$ is $f_{2} = f_{0} + f_{1} = 1$ , the Fibonacci number with subscript $3$ is $f_{3} = f_{1} + f_{2} = 2$ , the Fibonacci number with subscript $4$ is $f_{4} = f_{2} + f_{3} = 3$ , and so on with values $5, 8, 13, \dots$ .

(Note that there is a common alternative definition with $f_{0} = f_{1} = 1$ . These definitions are obviously very similar but incompatible. Please use mine.)

Here are some variants on the Fibonacci numbers.

Definition.

The Tribonacci numbers are the numbers $0, 1, 1, 2, 4, 7, 13, 24, 44, \dots$ , i.e. the case of $γ = 1$ in the sequence $(a_{n})$ where $a_{0} = 0$ , $a_{1} = 1$ , $a_{2} = γ$ and $a_{n + 1} = a_{n - 2} + a_{n - 1} + a_{n}$ for all $n ⩾ 2$ .

Definition.

The Padovan sequence is that of the numbers $0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, \dots$ , i.e. the case of $γ = 1$ in the sequence $(a_{n})$ where $a_{0} = 0$ , $a_{1} = 1$ , $a_{2} = γ$ and $a_{n + 1} = a_{n - 2} + a_{n - 1}$ for all $n ⩾ 2$ (so the sequence $a_{n}$ temporarily "forgets about" the last value).

Definition.

The Perrin sequence has the same recurrence relation as the Padovan sequence but starts with $a_{0} = 3$ , $a_{1} = 0$ , $a_{2} = 2$ .

Remark.

In all cases here, there is some variation where the sequence "starts" i.e. which value gets the index zero. Use my definitions please. They are not the only ones but seem to be at least as good as any other.

3. Programming

This is your opportunity to use C++ directly, without using any special macros for register machines, etc.

For the first two exercises, you might want to start with my program for $c_{n}$ as a model. Be careful to follow the instructions carefully, using int or double where required. Quiz questions ask about these, so it is worth saving these programs separately.

Exercise.

Write a program to make a table of Fibonacci numbers, similar to the program given for the $(c_{n})$ . Use int variables to store the numbers. You will of course need to save the previous two Fibonacci values as well as the current one (that's three int variables, as well as variables for the index and the maximum index). Save your program as fib_int.cpp and test it.

Exercise.

Modify your program for Fibonacci numbers so that it uses double variables to store the numbers. (it will continue to use int variables for the index and the maximum index). Print to 20 significant figures using cout.precision(20);. Save your program as fib_double.cpp and test it.

4. Assessment

It is all very well, running programs and getting them to type data to the console. However, for assessment purposes this really doen't work. The problem is I'd have to say exactly what to type, and it would have to be exactly rigt to the letter for my program to correctly read your program's answer. In my experience, only about 50% of students will successfully carry out that to the level of detail needed (no spelling errors, or blank lines, or spurious blank characters, no data swapped or given in the wrong order, etc.)

C++ has a mechanism to define and run functions and this is a much better way to do input and output and get two programs talking to one another. I am not expecting you to write your own functions this week (but you will do so next week) so instead I have provided an auxillary file, sa3.h, which you can download and save in the working folder that you are using, next to your main .cpp file, just like you did for register machines. It's a fully fledged set of functions for input/output for your program, not a set of macros, but you can use it just like "regmac.h". It will be explained in the lectures.

In both cases, for the Tribonacci numbers or the Padovan sequence, you should use "int" for the index variable(s) and "double" for all other real values.

If you are using Code::Blocks make a new project for each program, starting with the default "helloworld" main.cpp and copying the sa3.h file to the same folder as your main C++ source file. (If you are compiling from the command line it is up to you whether you make a new folder or whether all programs for this week all go in the same folder. But you will still need the sa3.h file in that folder.)
Check you understand how to use sa3.h by reading, copying and compiling the following example.

Example.

When $γ = 0$ this example calculates and prints the $n$ th triangle numbers 0,1,3,6,10,.... The general formula is given by $a_{0} = γ$ and $a_{n + 1} = a_{n} + n + 1$ . It also computes the ratio of the $n$ th and $n - 1$ st such numbers. You should find that this ratio tends to $1$ . (Why?)

#include <iostream>
#include "sa3.h"
using namespace std;

int main() {

  double gamma = 0;
  int maxn;
  
  // the next command gets the value of gamma
  get_gamma_value( gamma );

  // the next command gets the value of maxn
  get_final_index( maxn );

  int n = 0;
  double a = gamma;
  double aprev = 0.0; // "previous value"

  while ( n < maxn ) {
    // compute a_{n+1} from a == a_n and n
    aprev = a;
    a = aprev + n + 1;
    // update n
    n = n + 1;   
  }

  // print a_n, the nth triangle number
  print_answer( n, a ); 

  // print a_n/a_{n-1} or a/aprev which is 
  // the ratio of consecutive triangle numbers
  // note the order: n then a_{n-1} then a_n
  print_ratio( n, aprev, a ); 

  return 0;
}

The idea is that if you use the four special commands shown for input and output then your program can be tested correctly on another computer. It also means that you can put as many additional cout << ... statements in your program as you need and this will not get in the way of the testing. (But do not use any cin >> ... statements and make sure you use the four special commands in sa3.h in exactly the way used here, only once for each.)

Exercise.

Modify the programs you have already got to program the Tribonacci numbers with an arbitrary parameter $γ$ using the commands in sa3.h as shown. Investigate the limit of the ratio of consecutive terms for different values of $γ$ , especially for $γ = 1$ .

Exercise.

Modify the programs you have already got to program the Padovan numbers with an arbitrary parameter $γ$ using the commands in sa3.h as shown. Investigate the limit of the ratio of consecutive terms for different values of $γ$ , especially for $γ = 1$ .

The assessment will ask you to submit one of these programs. Make sure you read it and follow the instructions and specification exactly.

Always test all your programs carefully with as many possible input values you can think of, checking that the program gives answers that you expect (or at least can explain). Use a calculator or any other mathematics to check your program's output.

5. Summary

This was your first encounter with C++ in the official style. You should have learnt a lot about C++ in this exercise. In particular you have learnt about,

Use of variables, and how assignment works.
The basic use of loops.
Some of the limitations of int and double.
How to control the number of printed digits.