library(gmp)
N=1000
K=10
a=vector('list',N)
for(i in 1:K) a[[i]]=as.bigz(2^(i-1))
for(i in K:(N-1)){
a[[i+1]]=a[[i]]+a[[i-1]]+a[[i-2]]+a[[i-3]]+a[[i-4]]+a[[i-5]]+a[[i-6]]+a[[i-7]]+a[[i-8]]+a[[i-9]]
}

P0=vector('list',N)
for(i in 1:N) P0[[i]]=a[[i]]/2^i

# Pk(n+1)=1/2*P(k-1)(n)
P1=vector('list',N)
P1[[1]]=1/2
for(i in 1:(N-1)) P1[[i+1]]=(1/2)*P0[[i]]

P2=vector('list',N)
P2[[1]]=0
for(i in 1:(N-1)) P2[[i+1]]=(1/2)*P1[[i]]

P3=vector('list',N)
P3[[1]]=0
for(i in 1:(N-1)) P3[[i+1]]=(1/2)*P2[[i]]

P4=vector('list',N)
P4[[1]]=0
for(i in 1:(N-1)) P4[[i+1]]=(1/2)*P3[[i]]