# Tagged Questions

33 views

### Solving the recurrence $T(n)=4T(\frac{\sqrt{n}}{3})+ \log^2n$ [on hold]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated.
257 views

### Prove that the sequence with $T(0)=1$ and $T(n) = 1 + \sum_{j=0}^{n-1}T(j)$ is given by $T(n)=2^n$

$T(0)=1 \\ T(n) = 1 + \sum_{j=0}^{n-1}T(j) \\$ Show that $T(n) = 2^n$. I know how to prove this by induction, but I would like to know how to show this using first principles. Edit: The way I want ...
26 views

### Summation of series- substitution

If we have $\sum_{n=0}^{\infty}nf(n)=C, C\ne0\tag 1$, C is a constant, can we find a closed form for f(n)?. NB : Given condition is that $\sum_{n=0}^{\infty}f(n)$ converges to a constant value $K$ ...
64 views

### Summation of infinite series

If we know the series sum given below converges to a value $C$(constant) $$\sum_{n=0}^{\infty}a_n =C \tag 2$$ Can we generate following in terms of C. values of $a_n$ will tend to zero as n goes to ...
23 views

### Summation of infinte series

Sir, I have three infinite summation $A =J_1 \sum_{n=2}^\infty (n-1) f(n-2) \tag 1$ , $B =\sum_{n=0}^\infty f(n) \tag 2$ and $C =J_2\sum_{n=1}^\infty f(n-1) \tag 3$, with ...
28 views

### Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $|g(n) - n|$ is unbounded as $n$ grows. Let ...
34 views

### Finite geometric sequence with a ratio greater than 1

I am trying to solve the recurrence relation: $t(n)= 3T(n/2)+Cn$ (if $n>2$) $t(2)=C$ (otherwise) I know that there is the Master Theorem but I am trying to use the tree method. This ...
67 views

### Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
132 views

### Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)]$ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
37 views

### Finding an exact solution to a difference equation

How would I solve an equation of the form: $u(n+1)=1/2u(n)+(1/3)^n$ when $u(0)=1$? I got an answer of the form $u(n)= c + \sum(1/3)^j*2^{j-1}$ but believe this is incorrect?
59 views

### Summation in recurrence

I search the entire forum and couldn't fint a solution to this. Can you please help me solve this recurrence equation? $$T(n) = cn + \frac{4}{n^2}\sum_{k=0}^{n-1}T(k)$$
37 views

### A mixture of AP and GP

A battery loses $10$ mAh of after every hour when in use. The same battery loses $1\%$ of its current amount of charge every hour when not in use. Suppose that the battery is fully charged with ...
68 views

I read this on Wolfram Alpha. It states that: a quadratic recurrence relation uses a second degree polynomial to express $x_{n+1}$ as a function of $x_n$. A "quadratic map", then, is a recurrence ...
46 views

43 views

### Sum of second order recurrence relation, non constant coëfficients

Is there a general way to calculate the sum of a second order recurrence relation with non constant coëfficients? In my case, I have $$N_i = A_iN_{i-1} + B_iN_{i-2}.$$ Where I'm particularly ...
65 views

### How do I go about manipulating this summation equation to solve it?

In my textbook, Introduction to Algorithms, the following is shown: And I believe I understand that. However, I have a similar equation to the one on the first line, but instead of ...
69 views

### How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
89 views

### How do you solve a recurrence with a summation function inside

Show that $$t(n) = 1 + \sum_{ j=0}^{n-1} t(j)$$ is the same as $$t(n) = 2^n$$ Initial condition $t(0) = 1$
66 views

### Is it possible to get a 'closed form' for $\sum_{k=0}^{n} a_k b_{n-k}$?

This came up when trying to divide series, or rather, express $\frac1{f(x)}$ as a series, knowing that $f(x)$ has a zero of order one at $x=0$, and knowing the Taylor series for $f(x)$ (that is ...
78 views

### General solution to a recursive equation

What is the general solution of the following recursive equation? $$N(t)=(1+f)\cdot\left(N(t-1)-N(t-T)+N(t-T-1)\right)$$ By "general solution" I mean an equation where $N(t)$ stands alone on the ...
649 views

### Finding the sum- $x+x^{2}+x^{4}+x^{8}+x^{16}\cdots$

If $S = x+x^{2}+x^{4}+x^{8}+x^{16}\cdots$ Find S. Note:This is not a GP series.The powers are in GP. My Attempts so far: 1)If $S(x)=x+x^{2}+x^{4}+x^{8}+x^{16}\cdots$ Then ...
89 views

### Determine the integer part

Let $(a_n)$ be a sequence given by $a_1=\frac{1}{2}$ and $a_{n+1}=\frac{a_n^2}{a_n^2-a_n+1}$ , $n=1,2,...$ Let $b_n=a_1+a_2+...+a_n$ for each positive integer $n$ Determine the integer part $[b_n]$
65 views

### distance travelled after nth bounce

A ball is thrown vertically to a height of $625$ meters from ground. Each time it hits the ground it bounces $\frac{2}{5}$ of the height it fell in the previous stage. How much will the ball travel ...
44 views

### Split ${n\over2}\sum_{j\ge 1}2^{-j}(1-2^{-j})^{n-1}$ into oscillating terms.

Exercise 8.57 from Analysis of Algorithms (Sedgewick/Flajolet) asks for solving $p_n=2^{-n}\sum_k{n\choose k}p_k$ up to the oscillating term, for $p_0=0$ and $p_1=1$. I was able to find a functional ...
282 views

### A recurrence relation for Stirling numbers (2nd kind)

It is well-known that the Stirling numbers of the second kind satisfy the following (vertical) recurrence relation: $$\sum\limits_{r=k}^n \binom{n}{r}S\left( r,k\right) =S\left( n+1,k+1\right)$$ ...
68 views

### recurrence relation expanding $ij$

I need to solve this: $\displaystyle\sum\limits_{i=1}^n$$\displaystyle\sum\limits_{j=1}^n$$\displaystyle\sum\limits_{k=1}^{i\cdot j} 1$ How do I expand the $i\cdot j$ part? Am I right to do it this ...
247 views

### Whats better: 1 million dollars in a month or a penny(USD) doubled (and added) every day for 30 days?

THis is a question that I remember when I was in the 5th grade that tested our logical reasoning skills. And it is a simple choice knowing that the pennies doubling every day is an exponential ...
128 views

### General term of $a_n = 2a_{n-1} + 1$ [duplicate]

Find the general term of the sequence defined by: $a_n = 2a_{n-1} + 1$ where $a_1$ is given Thank You
77 views

### Help solving summation series of a recursive function

Yesterday in class, we were analyzing the Karatsuba multiplication algorithm and how it applies to recurrence equations. Time ran short, and I feel I missed how to solve the final summation. First, ...
170 views

### Solving the recurrence relation $p(n,m) = n \times \sum\limits_{k=n-1}^{m-1} p(n-1,k)$ where $p(1,m) = m$

I am trying to solve the following recurrence relation $$p(n,m) = n \times \sum\limits_{k=n-1}^{m-1} p(n-1,k)$$ $$p(1,m) = m$$ $$p(0,0)=0$$ Any hints or ideas? (Not a homework assignment) Edit: n ...
For first degree recurence relation it is as simple as $f(n)=a^n\cdot f(0)+b\dfrac{a^n-1}{a-1}$. But how do you solve second degree? For example f(n)=\begin{cases} 1,&\text{for }n=1\\ ...
### Counting binary sequences with no more than $2$ equal consecutive numbers
I invented the following problem, but I can't solve it. There are $n$ $1$'s and $n$ $0$'s and my question is what is the number of ways to arrange them avoiding $3$ equal consecutive numbers. So for ...