recategorized by
1,813 views
0 votes
0 votes
Find a recurrence relation for the number of strictly increasing sequences of positive integers that have 1 as their first term and n as their last term, where n is a positive integer. That is, sequences a1,a2,a3,a4....ak where a1 = 1, ak = n, and aj < aj+1 for j = 1,2,3,...k-1
recategorized by

2 Answers

1 votes
1 votes

a1=1

ak=n (it is not n th term of a)

So, every number should not be in a difference 1

But we can say 1st term+2nd term =3rd term

So, the recurrence relation an =an-1 + an-2

0 votes
0 votes

let the number of required sequences be Tk

Any strictly increasing sequences of postitive inegers a1,a2,...,awith a1=1 and ak=n  will either have n-1 or it won't have n-1 as its penultimate integer.

when it has ak-1 = n-1 in the sequence the number of such sequences i.e; a1,a2,...,ak-1,ak is counted as Tk-1. ( ak = n is fixed so we count the remaining part that ends in ak-1  = n-1 )

when n-1 is not present as the penultimate integer in the sequence, the number of sequnces is still Tk-1.  ( as the sequence effectively becomes a1,a2,...,ak-1 where ak-1 = n )

So,  Tk = Tk-1 + Tk-1 = 2Tk-1        with initial conditions T2 = 1.

Solving it in closed form gives  Tk = 2k-2 .

Related questions