I'm reading through Introduction to  and I got stuck on the following recurrence (exercise 4.4-5):  $$T(n) = T(n - 1) + T(n/2) + n$$  The exercise asks you to find the upper bound using the recurrence-tree method. I tried drawing one. It would have $2^n$  leafs if it was a complete binary tree (the height is $n$), but it is not. Furthermore, I cannot find a formula that expresses the complexity of each level like they do in the book.  After writing some code to calculate $T(n)$ and comparing it with different functions, I end up thinking that the complexity is exponential. Using $c2^n$ with the substitution method works out, but I'm not certain that this is a tight bound. I'm not certain that the tight bound is exponential either.  Can somebody help me out through the reasoning?  P.S.: If it matters, I'm not in school/university and this is not homework. I'm a (let's say) Ruby programmer who is self-studying to fill in his gaps in Computer Science.
62978
Using the recursion tree i tried solving this: $T(n)=T(n-1)+T(\frac{n}{2})+n$; the tree has two parts (branches) one that of $T(n-1)$ and other branch is of $T(\frac{n}{2})$. But as the term T(n-1) reach higher depth, I solved that part of the tree. Finally it resulted in O$(2^n)$ is it correct or is it $O(n^2)$? How can we solve it by substitution method?
45991
I got such recurrence equation which I cannot solve, I tried with mathematical induction, but I've got information, that this one is not linear and cannot be solve like that. And really have no idea how to do it.  $ \begin{cases} T(1)=1 \\ T(n)=2T(n-1)-4 \end{cases}$
3167
(Fitzpatrick Advanced Calculus 2e, Sec. 2.4 #12)  For $c \gt 0$, consider the quadratic equation $x^2 - x - c = 0, x &gt; 0$.  Define the sequence $\{x_n\}$ recursively by fixing $|x_1| \lt c$ and then, if $n$ is an index for which $x_n$ has been defined, defining  $$x_{n+1} = \sqrt{c+x_n}$$  Prove that the sequence $\{x_n\}$ converges monotonically to the solution of the above equation.  Note: The answers below might assume $x_1 \gt 0$, but they still work, as we have $x_3 \gt 0$.    This is being repurposed in an effort to cut down on duplicates, see here: .  and here: .
97667
When $t(n)$ is number of spanning trees in complete graph $K_n$ prove recursive formula for $t(n)$:  $$t(n) = {1\over (n-1)}\sum_{k=1}^{n-1} k(n-k){n-1 \choose k-1}t(k)t(n-k)$$ Could someone prove it or at least help somehow? I can use any method and Cayley's formula( $t(n)=n^{(n-2)}$) which I have already proven.
108367
Here's the problem:  1.Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one, two, or three steps at the time.  2.Explain how the relation is obtained  3.What are the initial condition (base case)  4.How many ways can this person climb a flight of nine stairs  5.Show that this number is an exponential function of n. That is, find a real constant $c &gt; 1$ such that this number is at least $c^n$.  I know the recurrence formula is $C_n = C_{n-1} + C_{n-2} + C_{n-3}$, but for question five, I used induction to show $C_n &gt;= c^n$ for some constant c, but  $C_n &gt;= c^{n-1} + c^{n-2} + c^{n-3} &gt;= c^n * (1/c + 1/c^2 + 1/c^3)$  since $1/c + 1/c^2 + 1/c^3$ is a less than 1 for $c &gt; 1$, I don't know how $C_n$ is guaranteed $&gt;= c^n$  Thanks!
10647
This looks like a question asked , but it isn't.  $$T(n)=\begin{cases} T (\sqrt{n}) + 1 \quad &amp; \text{ if } n&gt;1 \\  1 &amp; \text{ if }n=1\end{cases}$$  My professor gave this to me in class yesterday. This is where I'm stuck:   $$T(n) =  T(n^{1/2})+1 =  T(n^{1/4})+2 = T(n^{1/8})+3 = \dots =   T(n^{1/ 2 ^k})+k$$  Now this will continue till  $$n^{1/ 2 ^k}=1$$  How do I proceed ahead? If I take log on both sides, then RHS becomes zero. How do I solve the relation?  I don't want to use the Master theorem, I want to know where and why am I stuck.
57602
How do I find a recursion formula to solve the following question:  In how many sequences of length $n$, with elements from $\{{0,1,2,3,4}\}$, the difference between every 2 adjacent elements is $1$ or $-1$?  I've been trying to solve the problem for the last 5 hours maybe, I'm sure that I'm missing something..   This is a problem in combinatorics, and the solution must be by finding a recursion formula for the problem.   best solution I've come so far is that if we say that $a_n$ is the solution to the question, so let's count how many sequences of size $n-1$ there are that meet the requirement, and we complete the first element to make it a sequence of $n$ elements. so for $n-1$ there $a_{n-1}$ sequences, and for each sequence we have $2$ options to choose the first element (one option is to take a plus $1$ number from the number that start the $n-1$ sequence, and the other option to to take a minus $1$ number from the number that start the $n-1$ sequence), only problem as you figured out is that if the $n-1$ sequnce starts with $0$ or $4$ there is only $1$ option left for the first element in the sequnce.. so $a_n=2a_{n-1}$ won't work.  I think that the solution may involve using $2$ or maybe $3$ recursion formulas.  Hope I was clear enough.
19952
I'm doing some research about time complexity of algorithms and stumbled upon the following problem that I'm not able to solve:  Let $T(n) = T(n/3) + T(2n/3) + 5n$. prove that $T(n) = O(n log n)$  First, I made a recursion tree, which is the same as the one in the question:   I found out that each level costs $5n$ and that the leaves have different depths (The left path is the shortest with height $log_3 n$ and the one on the right is the longest with height $log_{\frac{3}{2}}n$).  Now, since we need an upper bound, I took the longest path of height $log_{\frac{3}{2}}n$. This gives total costs $5n \cdot log_{\frac{3}{2}}n$.  Now I want to prove with induction on $n$ that this is true. I proceeded in the following way:  Assume as induction hypothesis that $T(k) \leqslant 5k \cdot log_{\frac{3}{2}}k$ for $k &lt; n$. Then:  $T(n) \leqslant T(n/3) + T(2n/3) + 5n$ $=^{IH} \frac{5}{3}n log_{\frac{3}{2}}(\frac{n}{3}) + \frac{10}{3}n log_{\frac{3}{2}}(\frac{2n}{3}) + 5n$ $= \frac{25}{3}n log_{\frac{3}{2}} n - \frac{5}{3}n log_{\frac{3}{2}} 3 - \frac{10}{3}n log_{\frac{3}{2}} 3 + 5n$ $= \frac{25}{3}n log_{\frac{3}{2}} - 5n log_{\frac{3}{2}} 3 + 5n$  And this is certainly not smaller then or equal to $5n \cdot log_{\frac{3}{2}}n$. I've spend an entire day now on solving this recurrence relation, but nothing solved it so far. Could you help me solving this problem?
49471
I am not able to solve the above recurrence relation which involves $n$. The initial conditions $a_0 = 1, a_1 = 2, a_2 = 3$, for $n \geq 0$. Please try to give closed form in terms of arbitrary $a_i \geq 1 $ for $i \geq 0$
29669
If each term $a_k$ is either 0 or 1, how many sequences are there $a_1, a_2, \cdots$ , $a_n$ such that    $$a_1 \leq a_2 \geq a_3 \leq a_4 \cdots?$$   If we let $f_n$ be the number of ways for a n-term sequence, we can get a recursive formula.   Suppose $a_1=1$. Then $a_2=1$ and $a_3=0,1$ which is actually $f_{n-2}$.  Suppose $a_1=0$. If $a_2=1$, we get $f_{n-2}$ by similar reasoning. If $a_2=0$, $a_3=0$ so the cycle repeats. Thus the # of ways in this case is $f_{n-2}+f_{n-4}+f_{n-6}+\cdots$.  So the recursive formula will be $$f_n=2f_{n-2}+f_{n-4}+f_{n-6}+\cdots$$ and $f_1=2, f_2=3$. How do I get a closed form, or did I find the wrong recursive relation?
80297
A former student of mine was TA-ing an algorithms class last quarter and asked students to solve this famous recurrence relation:  $$T(n) = \sqrt n T(\sqrt{n}) + n$$  There are  and this question has already been asked here.  I was talking to my student about this problem and mentioned that it's quite hard to solve and is pretty dependent on the particular choices being made. As an example, I suggested this variant of a recurrence relation that was less simple to solve:  $$T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$$  The TA and I tried solving this recurrence for about an hour and a half without making any progress. Here are a few things we tried:   My approach to solving the initial recurrence relation was to draw out a recursion tree and notice that each level of the tree contributes $n$ to the total and that there are $O(\log \log n)$ layers, so the recurrence solves to $O(n \log \log n)$. When I tried doing this here, I noticed that the work per layer was no longer constant; instead, the top layer sums to $\sqrt{n}$, the second layer to $n^{3/4}$, the third to $n^{7/8}$, etc. We got stuck working with the summation $n^{1/2} + n^{3/4} + n^{7/8} + ...$. We tried using the iteration method to unroll the recurrence. With the original recurrence relation, this works out nicely; here, we got stuck at the same summation given above.   I'm completely stuck trying to figure out how to solve this recurrence relation. There's nothing riding on it per se - I don't need to solve it for any particular reason - but the fact that we arrived at it by a straightforward modification of a common algorithms problem set question makes it all the more enticing.  Any idea how to solve this recurrence?  Thanks!
38297
Suppose $a_0,a_1,a_2$ satisfy the recurrence $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}$ for $n\ge3$   Let $c_n=a_{n+1}-a_n$ for $n\ge1$ and $c_0=0$   Find a linear recurrence of degree at most 2 for the sequence $c_0,c_1,c_2,...$  I'm not entirely sure what they are asking for but I think it is asking for a recurrence relation for $c_n$ where the characteristic polynomial has degree at most 2.  I tried finding a closed form for $a_n$ to try and get rid of the $a_n$ in the $c_n$ equation, but I can't figure it out when the initial conditions aren't specified ($a_0,a_1,a_2$)  Any help would be appreciated!
106938
$a_0 = 1 \\ a_{n+1} = (n+1)a_n + 1 $  Could you help me solve this? And maybe someone know good source explaining how to solve recurrence relations?
105629
Solve $T(n)=T(n-2)+\frac{1}{\log(n)}$ for $T(n)$.   I am getting the answer as $O(n)$ by treating $1/\log(n)$ as $O(1)$. The recursive call tree of this is a lop-sided tree of height $n$. Hence, considering the amount of work done in each step, the answer comes out to be $O(n)$.  Please verify my answer, and tell me if I am correct.
72935
I have a sequence: $1,3,5,8,10,14,16,20,23,27,\dots$  I know that the recursive relation is:  $$p[i] := p[i-1] + \text{number of factors of $i$}, \quad \text{with $p[1]=1$.}$$  How do I solve this recursive relation in $O(n^{0.5})$ time? I have to write a program for it, and $n$ can be as large as $10^9$. So, some appropriate precomputation and prestorage is allowed, provided that they comply (memory and time wise) with the range of $n$.
69827
Write down the first five values of each of the following recursive sequences: $$ s_0 = 2, \quad   s_n = s_{n−1}^2 + s_{n−2}^2 + \cdots + s_0^2 $$ for all integers $n \geq 1$.  Approach: Say for $s_1= s_0^2 + s_1^2 + s_0^2$ which means $s_0^2 + s_0^2$ since $s_1$ isn't greater or equal to $1$.   So is the answer $8$ or just $s_0^2$ which will be $4$? I am confused by this part $[\ldots + s_0^2]$.
102358
I have an assignment problem that i have been fighting with for a while now..   I have this recursive function:  $$a_n=\begin{cases} 3,&amp;\text{if }n=0\\ 5,&amp;\text{if }n=1\\ 4a_{n-1}-4a_{n-2},&amp;\text{if }n\ge 2\;. \end{cases}$$  We define the generating function $$P(n)=\sum_{n=0}^\infty (a_n+a_{n+1})x^n$$  Now I need to use the definition of $a_n$ in the recursive function to show that $$P(n)=\frac{8-19x}{(1-2x)^2}$$  I cant really get to this result, and I have been trying all sorts of things by now, nothing really leading me anywhere..  I hope some of you can help me!  Thanks