What is wrong with my approach in recurrence?

51 Views Asked by At

A sequence of positive integers,a[1], a[2], a[3], . . . , a[n] is called a Special Sequence,i fa[1] divides a[2],a[2] divides a[3], and so on until a[n−1] divides a[n], and if all the elements are distinct. For example, (2,4,8,32) is a Special Sequence. But(4,2,8) is not, because 4 does not divide 2. Similarly (2,4,4,8) is also not Special,because the elements are not distinct.You need to find the find the number of special sequence for element sequence from set {1,2,3.......2K+1}.
My approach: Let $a_{2k+1}$ be the number of ways this could be done. Based on whether 2 is selected or not, I found the recursion formula to be:
$a_{2k+1}= a_{k}+ 1 + a_{2k}$, First for when only even numbers could be selected with it and 1, and other for selection of other 2k elements. However,the correct answer for k=7, i.e. 69 doesn't come and the correct answer for k=9,i.e.105 doesn't come either.What is wrong with my approach?