# Tagged Questions

Questions regarding functions defined recursively, such as the Fibonacci sequence.

56 views

27 views

34 views

### When is a recurrence the sum of the powers of the roots of a polynomial?

Newton's formula allows one to calculate the sum $S_n(P)$ of the $n$th powers of the roots of a given monic polynomial $P$ without finding the roots explicitly. (This works even when the roots ...
78 views

37 views

### How to solve this recurrence $T(n) = \log{n}*T(n/\log{n})+\sqrt{n}$

I tried substitution for $2^n$ or $2^{\log{n}}$ or even $2^{2^n}$ and it didn't work. Thanks! :)
35 views

### Trying to solve non-homogeneous linear recurrence relation with difficult non-homogeneous part

I have the following recurrence relation that I'm trying to solve: $$f(n)=2f(n-1)-f(n-2)-2$$ The homogeneous part is easy: The characteristic polynomial $r^2-2r+r=0$ has root $r=1$ with ...
28 views

28 views

### Recurrence: Theta of t(n) = 4t(n-1) -15

First let me start off by saying that I am using the substitution method to solve this equation.Although any other methods will be welcomed, this is just the particular method I feel comfortable with. ...
69 views

### Find recurrence relation with general solution $a_n=A+Bn+C2^n+\frac{1}{3}n2^{n-1}$

General solution is: $a_n=A+Bn+C*2^n+\frac{n}{3}*2^{n-1}$ Can you give me some tips on solving this? Any help would be appreciated.
21 views

### Express $T(n)$as a recurrence relation and derive and expression for $T(n)$ in terms of $n$.

Question: $T(n)$solves the problem by breaking it up into 4 sub problems of the same kind, each of size $n/4$. The solution to the original problem is obtained by combining the solutions of the $4$ ...
I got stucked a little with this question. would appreciate your help. the question is "find a recursive relation that counts how many sequences of order n above ${1,2,3,4,5,6,7}$ that don't contain ...
### second-order difference equation with variable coefficients $ax_{n+1}-(n+1+a)x_n+nx_{n-1}=-n$
The equation is: $ax_{n+1}-(n+1+a)x_n+nx_{n-1}=-n$, where $a$ is a constant and $0<a<1$. Any ideas on how to solve it? May be the z-transform is useful? Thank you! Using the difference operator ...