Articles of recursive algorithms

derivation of fibonacci log(n) time sequence

I was trying to derive following equation to compute the nth fibonacci number in O(log(n)) time. F(2n) = (2*F(n-1) + F(n)) * F(n) which i found on wiki form the fibonacci matrix equation stated there but i stuck in deriving it. I understood the derivation till the (-1)^n = F(n+1)*F(n-1) – F(n)^2 but then how […]

Algorithm for reversion of power series?

Given a function $f(x)$ of the form: $$f(x) = x/(a_0x^0+a_1x^1+a_2x^2+a_3x^3+a_4x^4+a_5x^5+…a_nx^n)$$ Let $A$ be an arbitrary (any) infinite lower triangular matrix with ones in the diagonal: $$A = \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 […]

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1,2,3} can […]

Stepping through the Josephus problem

I’m trying to figure out how the math in the Josephus problem works exactly. I first heard of it for programming purposes so that’s where my focus has been. The formula does seem to be recursive from what I can tell, and that’s what’s been killing me in solving it out by hand for any […]

Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

I have a series of numbers called the Foo numbers, where $F_0 = 1, F_1=1, F_2 = 1 $ then the general equation looks like the following: $$ F_n = F_{n-1}(F_{n-2}) + F_{n-3} $$ So far I have got the equation to look like this: $$T_n = T_{n-1}*T_{n-2} + T_{n-3}$$ I just don’t know how […]

Sum of the series formula

I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= \frac{\sum_{i=0}^{n-1}f(i,k-1)}{n} $$ and $ f(i,0) =i $ for all $i$. I did some paper work and brought the solution to $$f(n,k)=\frac{f(n-1,k-1)}{n} + \frac{(n-1)f(n-1,k)}{n} $$ But I need a closed form solution. Is it […]

Karatsuba multiplication with integers of size 3

I understand how to apply Karatsuba multiplication in 2 digit integers. $$\begin{array} \quad & \quad & x & y \\ \times & \quad & z & w \\ \hline \quad &?&?&? \end{array}$$ $$\begin{align} i & = zx \\ ii & = wy \\ iii & = (x+y)(w+z) \end{align}$$ and the result is $$i \cdot 10^2n […]

Find a Recurrence Relation

I want to find a recurrence relation for number of decimal numbers with length n, (we called $a_0$ ) that not includes 0 and any combination of 11,12, 21. i see the result is: $a_n=15a_{n-2}+7a_{n-1}$ How this was calculated? any hint or idea highly appreciated.

Finding a solution to $\sum _{n=1}^{n=k} \frac{1}{n^x}+\sum _{n=1}^{n=k} \frac{1}{n^y}=0$

Scroll down to the update to see what I am meaning. The Mathematica program below finds a solution to the equation: $$\sum _{n=1}^5 \frac{1}{n^x}+\sum _{n=1}^5 \frac{1}{n^y}=0$$ My question is if you can generalize this algorithm or iterated formula to partial sums of any length, not just $n=5$? The solution I have found is: $x=-2.30158037691463871425027298453 + […]

Repertoire method for solving recursions

I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics: \[ g(1)=\alpha \] \[ g(2n+j)=3g(n)+\gamma n+\beta_j \] \[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \] I have assumed the closed form to be: $$g(n) = A(n)\alpha+B(n)\gamma+C(n)\beta_0+D(n)\beta_1$$ Next i plugged $g(n)=1$ in the recurrence equations from which I obtained $\alpha=0 ,\beta_0=-2,\beta_1=-2$ and $\gamma=0$ […]