Linked Questions

1
vote
4answers
3k views

Solving the recurrence relation $T(n)=T(n-1)+cn$

I've solved the recurrence relation $T(n)=T(n-1)+cn$ (where T(1)=1), getting $1+c(\frac{n(n+1)}{2}-1)$, but I can't seem to get the pre-replacement step involving $k$. Here's what I have: ...
5
votes
4answers
208 views

How would you solve this recurrence equation: $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$

How would you solve $a_{n+1}-2a_{n}=6\cdot 5^n$ for $n\geq 1$ ? I don't understand the text in my textbook. I Would like somebody to explain it to me.
1
vote
4answers
369 views

Solving a recurrence of polynomials

I am wondering how to solve a recurrence of this type $$p_1(x) = x$$ $$p_2(x) = 1-x^2$$ and $$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x).$$ I am wondering, how could one solve such a recurrence. One way ...
3
votes
4answers
192 views

Solving Recurrence equation

I have a problem with this type of recurrence equation. Find the solution of recurrence equation: $$T(1)=2,$$ $$T(n+1)=T(n)+2n , \quad \forall n\geq 1$$ Indeed, I tired to Solving Recurrences ...
0
votes
3answers
580 views

non homogeneous recurrence relation

I am trying to solve the non-homogeneous linear recurrence relation: $$f(n) = 6f(n-1) - 5,\quad f(0) = 2.$$ How do I go about doing it? This is so different from solving a homogeneous recurrence ...
2
votes
3answers
70 views

solution of a recurrence

How might one solve the recurrence $x_{n+1} + x_n + 2^n = 0$ given the necessary initial conditions ($x_0$)? Possible ideas I have in mind: 1) Generating functions 2) Discrete Laplace ...
1
vote
6answers
372 views

Solving Recurrences using Telescoping/Backwards Substitution

Specifically, $$T(n)=3T(n-1)+1; \quad T(1)=1.$$ I have \begin{align*} T(n) & = 3T(n-1)+1 \\ & = 3(3T(n-2)+1)+1 \\ & = 9T(n-2)+4 \\ & = 9(3T(n-3)+1)+4 \\ & = 27T(n-3)+13 \\ & ...
1
vote
1answer
73 views

Solving Recursions like this

How can i solve this equation? I am really stuck $T(n) = T(n + 1) + T(n + 2) + 3n + 1$ $T(0)=2$ $T(1)=3$
2
votes
2answers
161 views

Solving recurrence equation with generating functions

$$a_{0}=0$$ $$a_{1}=0$$ $$a_{2}=-1$$ $$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_{n}=n$$ It's just that...I don't know what to do if there are $a_{n+1}$ instead of $a_{n-1}$, I don't know what to do with that ...
2
votes
1answer
117 views

Difficult partial solution to a reccurence equation

I am trying to help a friend of mine solve $$ a_n + 5 a_{n-1} + 6 a_{n-2} = 12n - 2(-1)^n$$ Now the homogenous solution is easy to find, and one just needs to solve the equation $r^2 + 5r + 6 = 0$ ...
0
votes
5answers
92 views

Find the solution to the recurrence relation: $a_n=3a_{n-1}+1; a_0=1$

$$a_n=3a_{n-1}+1; a_0=1$$ The book has the answer as: $$\frac{3^{n+1}-1}{2}$$ However, I have the answer as: $$\frac{3^{n}-1}{2}$$ Based on: Which one is correct? Using backwards substitution ...
1
vote
3answers
51 views

solve the non homogeneous recurrence relation

These recurrences should be simple to solve but I see a ton of different ways to do it, such as general solution, particular solution etc. We did not talk about these in class, just need to get the ...
0
votes
1answer
73 views

How do I solve this difference equation?

For a sequence $\{D_k\}$, if we have: $$D_k=pD_{k+1}+qD_{k-1}+1$$ and we know that $D_0=D_N=0$. Where $p+q=1$, and $N$ is known. How do I solve it?
1
vote
2answers
56 views

Solving recurrence $T(n)=T(n-1)+3^{n-1}$

I have trouble solving following recurrence. $$T(n)=T(n-1)+3^{n-1}$$ So far I tried annihilators but it doesn't work.
1
vote
2answers
35 views

Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$

Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$ if $s_1 = 0, s_2 = 0, s_3 = 1$ I have attempted to use $p_n = c2^{n-2} - d$ [where $h_n = A(3)^n$, but to no avail] - i ended up with ...