Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I found these two recurrence relations in an old textbook and was hoping someone could show me how to solve them for their closed form. If not, a final answer would also be appreciated, as it helps me reason out the iterative process (I've tried using online calculators to give me an answer but I haven't had the best of luck).

$T(n) = T(\frac{n}{2}) + \log_2{n}, T(1) = 1$ and n is a power of 2

$T(n) = eT(n-f)+g, T(0) = 0$ and e,f,g > 0 and n is a multiple of f

share|improve this question
    
So $f$ is an integer and the second relation amounts to $T(kf)=eT((k-1)f)+g$? All you can hope is to find a closed form for $T(kf)$ and not every $T(n)$. –  1015 Feb 6 '13 at 2:57
    
Likewise, your first relation will only help you compute $T(2^k)$. –  1015 Feb 6 '13 at 3:00
add comment

2 Answers

up vote 2 down vote accepted

The second relation reads $T(kf)=eT((k-1)f)+g$ for all $k\geq 0$. Write $T(kf)=x_kg$. Then $x_0=0$ and $x_k=ex_{k-1}+1$.

Case 1: $e=1$ then $x_k=k$ (induction) and so $$T(kf)=kg.$$

Case 2: $e\neq 1$ then $\frac{1}{1-e}$ is a constant solution and the general solution of the homogeneous relation$x_k=ex_{k-1}$ is the geometric sequence $\lambda e^k$. So $x_k=\frac{1}{1-e}+\lambda e^k$. For $k=0$, we find $0=\frac{1}{1-e}+\lambda $, so $x_k=\frac{1-e^k}{1-e}$. Hence $$ T(kf)=\frac{(1-e^k)g}{1-e}. $$

Your first relation tells you actually that $T(2^k)=T(2^{k-1})+k$. Setting $y_k=T(2^k)$, we have to solve $y_k=y_{k-1}+k$ with $y_0=1$. So $y_k=1+1+2+\ldots+k=1+\frac{k(k+1)}{2}$ (induction). So we have $$ T(2^k)=1+\frac{k(k+1)}{2}=\frac{k^2+k+2}{2}. $$

Edit: There is a general technique to solve linear recurrence relations of order $n\geq 1$ of the type $$ x_{k}=c_{1}x_{k-1}+\ldots+c_{n-1}x_{k-n+1}+c_nx_{k-n}+C\quad\forall k\geq n. $$ This should be seen, somehow, as a discrete linear ODE of order $n$.

The key object to consider is the characteristic polynomial of the homogeneous equation: $$ x^n-c_{n-1}x^{n-1}-\ldots-c_1x-c_0. $$

Strategy:

1) Find a particular solution. This depends very much on $C$. This could actually depend on $k$, in the most general situation. Here $C\neq 0$ is constant, and there are several cases to consider:

  • If $P(1)\neq 0$ (case 2 above), then look for a particular solution which is constant. You will find that $x_k=\frac{C}{P(1)}$ works.

  • If $P(1)=0$ and $P'(1)\neq 0$ (case 1 above), then look for a particular solution of the form $x_k=Ak$. You'll find $A$.

  • If $P(1)=P'(1)=0$ and $P''(0)\neq 0$, look for a particular solution of the form $x_k=Ak^2$.

  • And so on...

2)Solve the homogeneous equation: $$ y_{k}=c_{1}y_{k-1}+\ldots+c_{n-1}y_{k-n+1}+c_ny_{k-n}\quad\forall k\geq n. $$ Theory tells you that this is an $n$-dimensional subspace of the vector space of all complex sequences. In the case where the roots of the characteristic polynomial are pairwise distinct $r_1,\ldots,r_n$, the general homogeneous solution can be written: $$ y_k=A_1r_1^k+\ldots +A_nr_n^k. $$ If there are repeated roots, say $r_j$ with multiplicity $3$, then the correpond ing term is of the form $(A_jn^2+B_jn+C_j)r_j^k$.

3) The general solution of your initial relation is the sum of the particular solution found in 1) and of the general homogeneous solution found in 2). If there are initial conditions ($x_0$, $x_1$ given...), this will lead to restricitions on the constants $A_j$, or even to a full determination of them.

Note: Here, it is actually pretty simple since it is of order $1$. For $x_k=ex_{k-1}+1$, the characteristic polynomial is $$ P(x)=x-e. $$ - Case 1: $e=1$ and then $P(1)=0$ and $P'(1)\neq 0$ so we look for a particular solution of the form $x_k=Ak.$ We find that $A=1$ and $x_k=k$ works. The homogeneous equation clearly leads to a general constant homogeneous solution $y_k=B$. Now your general solution is $x_k=k+B$. The initial condition $x_0=0$ yields $B=0$ so $x_k=k$.

(Note that like I said initially, it is easy to see and prove by induction that $x_k=x_{k-1}+1$ with $x_0=0$ leads to $x_k=k$).

  • Case 2: $e\neq 1$ so that $P(1)\neq 0$. Then a particular solution is the constant sequence $x_k=1/P(e)=1/(1-e)$ and the general homogeneous solution is $y_k=Ae^k$. SO the general solution is $x_k=Ae^k+1/(1-e)$. And we find $A$ by the initial condition $x_0=0$.
share|improve this answer
    
Can we express these solutions in terms of $n$? –  Bob John Feb 6 '13 at 3:20
    
For $\,k=4\,$ I get $\,T(16)=11\,$ , so at least either one of you or I are wrong.... –  DonAntonio Feb 6 '13 at 3:23
    
Also, I believe the first solution should be $T(2^k) = \frac{k(k+1)}{2}+1$, but I'm still not sure how to express this in terms of $n$. –  Bob John Feb 6 '13 at 3:27
    
Yes, you are both right. It should be $1+\frac{k(k+1)}{2}$. I did $T(1)=0$ instead of $T(1)=1$ the first time. –  1015 Feb 6 '13 at 4:17
1  
@BobJohn Your relations do not say anything about the other values of $T(n)$. They could be anything. –  1015 Feb 6 '13 at 4:19
show 7 more comments

For example the firt one:

$$T(1)=1\;\;,\;\;T(2)=T(1)+\log_22=1+1=2\;\;,\;\;T(4)=T(2)+\log_24=2+2=4$$

$$T(8)=T(4)+\log_28=4+3=7\;\;,\;\;T(16)=T(8)+\log_216=7+4=11$$

So the sequence seems to be $\,1,2,4,7,11,16,22,\,\ldots,a_{n-1}+n-1\,\ldots\,$

share|improve this answer
    
How do we express the answer in terms of $n$? –  Bob John Feb 6 '13 at 3:24
    
Note that $1+2+\ldots+n=\frac{n(n+1)}{2}$. –  1015 Feb 6 '13 at 4:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.