12.1. Recursion http://www.ck12.org
- You can choose any starting positive integer you like. Here are the sequences that start with 7 and 15.
7 , 22 , 11 , 34 , 17 , 52 , 26 , 13 , 40 , 20 , 10 , 5 , 16 , 8 , 4 , 2 , 1 , 4 , 2 , 1 ...
15 , 46 , 23 , 70 , 35 , 106 , 53 , 160 , 80 , 40 , 20 , 10 , 5 , 16 , 8 , 4 , 2 , 1 , 4 , 2 , 1 ...
You could make the conjecture that any starting number will eventually lead to the repeating sequence 4, 2, 1.
This problem is called the Collatz Conjecture and is an unproven statement in mathematics. People have used
computers to try all the numbers up to 5× 260 and many mathematicians believe it to be true, but since all natural
numbers are infinite in number, this test does not constitute a proof.
Practice
Write a recursive definition for each of the following sequences.
- 3, 7 , 11 , 15 , 19 ,...
- 3, 9 , 27 , 81 ,...
- 3, 6 , 9 , 12 , 15 ,...
- 3, 6 , 12 , 24 , 48 ,...
- 1, 4 , 16 , 64 ,...
- Find the first 6 terms of the following sequence:
b 1 = 2
b 2 = 8
bk= 6 bk− 1 − 4 bk− 2 - Find the first 6 terms of the following sequence:
c 1 = 4
c 2 = 18
ck= 2 ck− 1 + 5 ck− 2
Suppose the Fibonacci sequence started with 2 and 5. - List the first 10 terms of the new sequence.
- Find the sum of the first 10 terms of the new sequence.
Write a recursive definition for each of the following sequences.These are trickier! - 1, 4 , 13 , 40 ,...
- 1, 5 , 17 , 53 ,...
- 2, 11 , 56 , 281 ,...
- 2, 3 , 6 , 18 , 108 ,...
- 4 , 6 , 11 , 18 , 30 ,...
- 7, 13 , 40 , 106 , 292 ,...