1
vote
0answers
21 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
31 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
125 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
56 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
36 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
59 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
42 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
103 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
55 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
42 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
63 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
67 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
85 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
77 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
641 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
43 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
279 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
242 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
74 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
382 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
441 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 ...