# Tagged Questions

Questions dealing with recursive algorithms. Their analysis often involves recurrence relations, which have their own tag.

6answers
2k views

### How to solve this recurrence relation? $f_n = 3f_{n-1} + 12(-1)^n$

How to solve this particular recurrence relation ? $$f_n = 3f_{n-1} + 12(-1)^n,\quad f_1 = 0$$ such that $f_2 = 12, f_3 = 24$ and so on. I tried out a lot but due to $(-1)^n$ I am not able to ...
3answers
2k views

### Solving a Recurrence Relation/Equation, is there more than 1 way to solve this?

1) Solve the recurrence relation $$T(n)=\begin{cases} 2T(n-1)+1,&\text{if }n>1\\ 1,&\text{if }n=1\;. \end{cases}$$ 2) Name a problem that also has such a recurrence relation. The ...
2answers
1k views

### Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
6answers
998 views

### Non-literal applications of “Shortest Path” algorithm?

It's obvious that it's used in stuff like Google Maps, but what are some more metaphorical applications where you're minimizing the path between nodes (which can represent anything)
3answers
10k views

3answers
1k views

### Karatsuba vs. Schönhage-Strassen for multiplication of polynomials

I am wondering how to most effectively multiply two polynomials with several $100$'s of coefficients, each coefficient having $1000$-$2000$ decimal digits. I know Schönhage-Strassen begins to ...
3answers
850 views

### 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 ...
1answer
157 views

### What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?

If you have the following recurrence relations : $a(n+1)= a(n) b(n)$ $b(n+1)= a(n) + b(n)$ How do you find the form of $a(n)$ and $b(n)$ ? I suspect there isn't a closed form , but a infinit sum ...
3answers
410 views

### Solving recurrence relation: Product form

Please help in finding the solution of this recursion. $$f(n)=\frac{f(n-1) \cdot f(n-2)}{n},$$ where $f(1)=1$ and $f(2)=2$.
1answer
252 views

### Finding $a_n$ for very large $n$ where $a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3}$

I have a recurrence relation, $$a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3}$$ for $n>3$ and $a_1 = 0, a_2 = 0, a_3 = 1$ I have to find the value of $a_n$ for very large values of n. I tried ...
2answers
957 views

### unorthodox solution of a special case of the master theorem

I am asking for references regarding a special case of the master theorem. This theorem seems to appear quite a lot on this site, prompting me to study it in more detail, e.g. see my posts here and ...
2answers
182 views

0answers
875 views

### When do ﬂoors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...