Recursive Function for Pyramid-Scheme

1.3k Views Asked by At

consider a group which has 1 user. each month, every user can bring another user to join the group. the user that has been joined for 3 months, should leave the group. calculate the total membership count, after 30 months.

MONTH    0    1    2    3    4    5    6    7
TOTAL    1    2    4    8    14   26   48   88

If I'm right with those numbers, from month 1, the recursive function would be f(n) = f(n-1) + f(n-2) + f(n-3)

Is it correct? if yes then how to calculate the new memberships and leavings counts?

UPDATE

I found a solution..., correct?

n > 3 | G(n) = G(n-1) + G(n-2) + G(n-3) //total count, remove after month 3

n > 3 | L(n) = L(n-1) + L(n-2) + L(n-3) //sum of people left the group per month

n > 3 | N(n) = T(n-1) //new people per month

n > 3 | T(n) = G(n) - L(n) //total count, remove on month, third

MONTH    1    2    3    4    5    6    7
------------------------------------------
G        2    4    8    14   26   48   88
N        1    2    4    7    13   24   44
L        0    0    1    1    2    4    7
T        2    4    7    13   24   44   81
1

There are 1 best solutions below

4
On

I think you're whit numbers but the recursive algorithm is: ($F^0_n:$new members , $F^1_n:$1 month members , $F^2_n:$2 month members , $F^3_n:$3 month members)

$F^0_n=F^0_{n-1}+F^1_{n-1}+F^2_{n-1}$

$F^1_n=F^0_{n-1}$

$F^2_n=F^1_{n-1}$

$F^3_n=F^2_{n-1}$

$f_n=F^0_{n}+F^1_{n}+F^2_{n}+F^3_{n}$

This equations can reduce to

$A_n= 2A_n-2B_n$

$B_n=A_{n-4}-B_{n-4}$
($A_n=f_n$)
($B_n=F^3_n$)

Which is easier to solve.