Question

Nathan has two parents, four grandparents, and so on. Explain how you can write both an explicit formula and a recursive formula that represents the number of ancestors Nathan has if we go back n generations.

Answer 1

Explicit formula

f(n) = 2*2⁽ⁿ⁻¹⁾

Recursive formula

f(n) = aₙ₋₁ * r

Explanation:

Since, Nathan has two parents, four grandparents, and so on, it would form a Geometric Progression (GP) series for the number of Nathan's ancestors as below:-

2, 4, 8, 16, 32, ....

First term (a₁) = 2

Common Ratio (r) =
`(a_(2) )/(a_1)`

=
`(4)/(2)`

= 2

So,

Number of ancestors of Nathan if we go back n generations = a₁r⁽ⁿ⁻¹⁾

Plugging in the values of a₁ and r, we get

f(n) = 2*2⁽ⁿ⁻¹⁾ [Explicit formula]

Now,

A geometric progression (GP) series is of the form,

a, ar, ar², ar³, ar⁴, ar⁵........

in which the first term a₁=a and other the terms are obtained by multiplying with r.

Observe that each term is r times the previous term. So, to get the
`n_(th)` term, we multiply
`(n-1)_(th)` term by r.

i.e. aₙ = aₙ₋₁ * r

=> f(n) = aₙ₋₁ * r [Recursive formula]