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

learn more… | top users | synonyms

14
votes
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 ...
9
votes
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 ...
9
votes
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 ...
8
votes
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)
8
votes
3answers
10k views

Using Horner's Method

I'm trying to evaluate a polynomial recursively using Horner's method. It's rather simple when I have every value of $x$ (like: $x+x^2+x^3...$), but what if I'm missing some of those? Example: $-6+...
8
votes
1answer
803 views

Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
8
votes
2answers
2k views

Numerical method for finding the square-root.

I found a picture of Evan O'Dorney's winning project that gained him first place in the Intel Science talent search. He proposed a numerical method to find the square root, that gained him $100,000 ...
8
votes
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 ...
8
votes
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 ...
8
votes
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 ...
7
votes
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$.
7
votes
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 ...
7
votes
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 ...
7
votes
2answers
182 views

$ T(n)= T(\log n)+ \mathcal O(1) $ Recurrence Relation

what is the solution of following recurrence relation? $$\begin{align} T(1) &= 1\\ T(n) &= T(\log n) + \mathcal O(1) \end{align}$$ a) $O(log n)$ b) $ O (log^* n) $ c) $ O (log^2 n) $ d) $ ...
7
votes
3answers
310 views

Error accumulation in an approximating numerical algorithm for $y_n =\int_{0}^{1} \frac{x^n}{x+10} dx $

Consider the problem of calculating the integral $$y_n =\int_{0}^{1} \dfrac{x^n}{x+10} \mathrm{d}x $$ for a positive integer $n$. Observe that $$y_n + 10y_{n-1} = \int_{0}^{1} \dfrac{x^n +10x^{n-1}}{...
7
votes
1answer
160 views

Another recurrence… $T(n)=\sqrt{2n} \cdot T(\sqrt{2n}) + \sqrt{n}$

I'm trying to solve the following recurrence : $$T(n)=\sqrt{2n}\cdot T(\sqrt{2n}) + \sqrt{n}$$ I've tried substituting $n$ for some other variables to transform the above to something easier without ...
6
votes
4answers
234 views

Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

This question appears also in http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this ...
6
votes
3answers
388 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = k_{0}\...
6
votes
1answer
580 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
6
votes
1answer
7k views

Show that the solution to $T(n) = T(n - 1) + n$ is $O(n^2)$

Hello and thanks for taking the time to answer my question. The question is really the title itself. We're studying about solving recurrences using the method of substitution and induction. How can I ...
6
votes
1answer
189 views

Flip all to zero

I have a square grid of size $N$, with rows numbered from $0$ to $N - 1$ starting from the top and columns numbered from $0$ to $N - 1$ starting from the left. A cell $(u, v)$ refers to the cell that ...
6
votes
1answer
127 views

Is every context free language equivalent to one whose grammar has only one non-terminal symbol?

A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting ...
6
votes
2answers
3k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
6
votes
0answers
164 views

Generating Functions, Recursive Polynomials

At the CMFT international conference in Turkey (2009), the following open problem was given: Show that $$p_n(x):=\sum_{k=0}^n \frac{(n-k)^k}{k!}x^{n-k}$$ has only real simple zeros for every $n$. ...
5
votes
5answers
2k views

Where do the first two numbers of Fibonacci Sequence come from? [duplicate]

I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
5
votes
3answers
11k views

Worst case complexity of the quicksort algorithm

Good evening, I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of ...
5
votes
3answers
280 views

Recursion with Random number?

function foo(n) if n = 1 then return 1 else return foo(rand(1, n)) end if end function If ...
5
votes
1answer
183 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
5
votes
2answers
306 views

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(...
5
votes
3answers
184 views

How does $\tbinom{4n}{2n}$ relate to $\tbinom{2n}{n}$?

I got this question in my mind when I was working on a solution to factorial recurrence and came up with this recurrence relation: $$(2n)!=\binom{2n}{n}(n!)^2$$ which made me wonder: is there also a ...
5
votes
4answers
2k views

A 3rd grade math problem: fill in blanks with numbers to obtain a valid equation

Even though this is a 3rd-grade math problem, people found it extremely hard. Any people have a solution, or algorithm is welcome. I'll try make a program base on the algorithm and see if it's correct....
5
votes
2answers
431 views

Characteristic equation. What is it?

Consider a recursive equation: $$ a_n = A a_ {n-1} + Ba_ {n-2} $$ And for this type of equation, there is characteristic equation: $ x ^ 2 = Ax + B $. What does exactly means that this equation is ...
5
votes
3answers
191 views

Need help about solving a recurrence relation

I have a recurrence relation which is like the following: $$ T(n) = 2T(n/2) + \log_2 n. $$ I am using recursion tree method to solve this. And at the end, i came up with the following equation: $$ T(...
5
votes
1answer
218 views

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 ...
5
votes
1answer
554 views

How many distinct ways to climb stairs in 1 or 2 steps at a time? (Fibonacci puzzle)

There is a very interesting puzzle for fibonacci sequence ...
5
votes
1answer
2k views

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 &?&?&...
5
votes
3answers
653 views

Can someone intuitively explain the towers of Hanoi and how a proof by induction can be used?

I'm having trouble understanding precisely how the proof by induction is used to show that it takes at most $2^n-1$ moves to get all the disks from one peg to another. Are there any helpful sources ...
5
votes
2answers
434 views

Karatsuba Multiplication

Karatsuba's equation to reduce the amount of time it takes in brute force multiplication is as follows (I believe this is a divide-and-conquer algorithm): $$ x y = 10^n(ac) + 10^{n/2}(ad + bc) + bd $...
5
votes
3answers
114 views

Recursion, multiplication and exponential

The set $F_{n}$ of primitive recursive function symbols of arty $n$ can be defined inductively as \begin{array}[lr] & Z, \text{Succ} \in F_{1} & \\ \pi_{j}^{n} \in F_{n} \quad \text{for each} \...
5
votes
2answers
387 views

Determining a recurrence relation (Homework)

Let ${d_n}$ be the number of DNA strings of length n that contain a pair of consecutive nucleotides of the same type. There are four symbols used in strings of DNA: A, C, G, T. The nucleotides are ...
5
votes
2answers
370 views

Can this be solved by induction? (number of ways of cutting a rod into pieces)

I am reading an algorithm example. The example is about Rod cutting. The idea is that a steel rod can either be sold as it is, or be cut into integral pieces and ...
5
votes
1answer
783 views

Applying a Math Formula in a more elegant way (maybe a recursive call would do the trick)

This is my first post in Math section. I've been redirected here from StackOverflow, users from there suggested me to ask here. This could appear a little bit complex at first sight but afterall ...
5
votes
1answer
285 views

Nesting functions to understand nesting series

So I am working on a problem that involves an expression that has a "nested" sigma notation. Maybe "nested" isn't the correct word, because you start with an input (of your choosing) and the output ...
5
votes
1answer
2k views

Fibonacci with Mortal Bunnies

I am trying to understand a twist on the Fibonacci bunnies scenario, where the bunnies die x generations after their birth (where x is a positive integer). An example is shown here. I understand the ...
5
votes
1answer
153 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} \binom{n-1}...
5
votes
2answers
477 views

Has anything useful come from Ackermann's Function?

Here is the function: if (m == 0) return n + 1; else if (n == 0) return A(m-1, 1); else return A(m-1, A(m, n-1)); This seems like an interesting ...
5
votes
1answer
3k views

Quick sort algorithm average case complexity analysis

This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications". The quick sort is an efficient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm ...
5
votes
1answer
84 views

After $n$ iterations of the continued fraction algorithm, what kind of rational numbers will have terminated?

For a positive real number $r_0$, we have the continued fraction recursive algorithm: \begin{align} &r_n\in\mathbb{Z}\implies\text{terminate the algorithm}\\ &\text{else } r_{n+1} = \frac{1}{...
5
votes
0answers
134 views

Is there a simplification for the coefficients generated with the Mandelbrot iteration rule?

The Mandelbrot Set is obtained using the equation $z_n=z_{n-1}^2+c$ for some constant $c \in \mathbb{C}$ with $z_0=0$. Therefore, $z_1=c$, $z_2=c^2+c$, $z_3=c^4+2c^3+c^2+c$, etc. I have a function ...
5
votes
0answers
875 views

When do floors 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 ...