2
votes
0answers
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.
5
votes
5answers
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 ...
1
vote
1answer
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$ ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
3answers
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?
0
votes
1answer
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) $$
2
votes
2answers
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 ...
0
votes
1answer
68 views

Solve a Quadratic map

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 ...
0
votes
0answers
46 views

Removing the Summation (Closed Form)

The following question from "Combinatorics of Permutations" : $$ E[X] = \sum\limits_{k = 2}^n \frac{k\cdot T(n,k)}{n!} $$ where $$ T(n,k) = k \cdot T(n-1, k) + 2 \cdot T(n-1, k-1) + (n-k) \cdot ...
0
votes
1answer
29 views

Solving thus summation

$F_1 = 1, F_2 = 2, F_i = F_{i - 1} + F_{i - 2} (i > 2)$. A new number sequence $Ai(k)$ by the formula: $A_i(k) = F_i × i^k (i ≥ 1)$.I need to calculate the following sum: $A_1(k) + A_2(k) + ...
0
votes
2answers
47 views

Recurrence relation - Show that a sum of a sequence is zero

We are given the following sequence: $f(n)=4f(n-1)-5f(n-2)$, $f(0)=f(1)=a$ where $a$ is some value in $\mathbb C$. We are asked to show that $$\sum_{n=0}^{\infty}\frac{f(n)}{3^n}=0$$ First thing I ...
2
votes
3answers
107 views

Solving recurrence relation with generating functions - Nearly got the answer

I'm trying to solve the following recurrence relation (Find closed formula) using generating functions: $f(n)=10f(n-1)-25f(n-2)$, $f(0)=0$, $f(1)=1$ I'm having a small difficulty at the end and can ...
0
votes
1answer
43 views

What's the maths symbol for alternation of product and sums?

Is there a mathematics symbol for referring to the equation below? (((((((((((100*y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x) *y-x = 0, x = 9.8 I've tried using capital ...
3
votes
0answers
44 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
0
votes
1answer
56 views

Recurrence relation - repeated substitution

I am having some trouble with solving a recurrence relation with repeated substitutions. $$a_n = 3\cdot2^{n-1}-a_{n-1}$$ I show some work: $$a_n = 3\cdot2^{n-1} ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
2
votes
3answers
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$
1
vote
1answer
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 ...
0
votes
1answer
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 ...
32
votes
1answer
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 ...
-1
votes
1answer
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]$
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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) $$ ...
1
vote
3answers
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 ...
5
votes
2answers
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 ...
0
votes
2answers
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
2
votes
2answers
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, ...
1
vote
2answers
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 ...
2
votes
3answers
387 views

How to solve second degree recurrence relation?

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\\ ...
17
votes
3answers
446 views

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 ...