# Tag Info

## Hot answers tagged recurrence-relations

3

I have an almost closed form. It uses the functions $z_2(n)$, which is the number of zeros in the binary representation of $n$ (after the first non-zero digit, of course) and $Z_2(n)=\sum_{i=1}^n z_2(n)$. I am quite sure these can be calculated quickly, but I'll leave that to you. Section 1: A Closed Form For S(n). Running off of Michael Biro's answer, ...

3

Your decomposition is incorrect. \begin{align} \frac{rBx}{(1-rx)(1-x)^2} & = \dfrac {U}{1-rx} + \dfrac V{x-1} + \dfrac W{(x-1)^2}\\ \\ &= \frac{U(x^2-2x+1)+ V(1 - rx)(x-1) + W(1-rx)}{(1-rx)(1-x)^2}\end{align} Now try and solve for $U, V, W$.

3

We have: $a_n\\= (a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) +\cdots + (a_2 - a_1) + a_1\\= (1+2^{n-1}) +(1+2^{n-2}) +\cdots +(1+2^1) + 2\\= n+1 + 2(1+ 2 + \cdots + 2^{n-2})\\= n+1+2(2^{n-1}-1)\\= n-1+2^n$.

3

There're at least two four commonly used methods: generating functions looking for solutions in a particular form: $n^k\alpha^n$ with $k\in\mathbb N$ and $\alpha\in\Bbb R$. Z-transform. Thank you, @Omnomnomnom. The annihiliator method/characteristic equations (even though they are closely related to the second method). Thank you, @anorton. The wikipedia ...

3

Noting that $T(1)=1=\lfloor \sqrt{1}\rfloor$, so far, you've narrowed it down to the form (although you forgot the floor symbols, which are important): $$T(n)=\sum_{i=1}^{n}\lfloor\sqrt{n}\rfloor$$ which is correct; to solve this, notice that if we calculated $T(4^2-1)=T(15)$ thusly, for instance, the sum would expand as (after we lay it out very ...

3

Well, this post was edited several times while I wrote this, but I just assume that the corrected question is the one Hurkyl commented. Equation $f_m(x)=x$ has no integer solution $x$ s.t $|x|>1$ because $|x|>1 \Rightarrow |2x^2-1|>|x|>1$. Hence we just try calculating $f_m(x)$ with $x=0,-1$, and if you sensed that $x=\cos \theta \Rightarrow ... 2 This equation $$f'(x)=2f(2x+1)-2f(2x-1), \quad f(0) = 1, \tag{*}$$ has a finite solution which is also known as the$\mathrm{up}(x)$or$\mathrm{hut}(x)$function. It has compact support$\mathrm{supp}\,\mathrm{{up}}(x)=[-1,1]$and its Fourier transform is$\hat{f}(t)=\prod\limits_{k=1}^{\infty}\mathrm{sinc}{(t\cdot ...

2

Since ultimately you would like the denominators of the partial fractions to have the form $1-ax$, I’d start by multiplying top and bottom by $-1$ to get $$\frac8{1-2x-3x^2}\;.$$ Now use your roots to factor the denominator, then set up the partial fraction decomposition: $$\frac8{1-2x-3x^2}=\frac8{(1-3x)(1+x)}=\frac{A}{1-3x}+\frac{B}{1+x}\;.$$ Now just ...

2

Without any of the usual theoretical tools, you’ll need to do a bit of pattern-recognition. Notice the following pattern: \begin{align*} a_0=0&\\ a_1=1&=2\cdot0+1\\ a_2=1&=2\cdot1-1\\ a_3=3&=2\cdot1+1\\ a_4=5&=2\cdot3-1\\ a_5=11&=2\cdot5+1\\ a_6=21&=2\cdot11-1 \end{align*} This suggests the first-order recurrence ...

1

One way to do this is to use generating functions. Let $G(x)=\sum_{n=0}^{\infty}a_nx^n$. We have the relation : $a_n=a_{n-1}+2a_{n-2}$. Multiply both sides by $x^n$ and summing from $n=2$ to $\infty$ we get: $G(x)-a_0-a_1x=x(G(x)-a_0)+2x^2G(x)$. Then we get: $G(x)(1-x-2x^2)=a_0-a_0x+a_1x=x$ (since $a_0=0,a_1=1$). So, ...

1

Consider the generating function $f(t)=\sum_{n=0}^\infty x_n t^n$, which will satisfy: $$\sum_{n=0}^\infty x_{n+2}t^n - \sum_{n=0}^\infty 3x_{n+1} t^n + \sum_{n=0}^\infty 2x_nt^n = \sum_{n=0}^\infty n t^n$$ The RHS is simply $\frac{t}{(1-t)^2}$. The LHS, however, is $$t^{-2}(f(t)-x_1t-x_0) - 3t^{-1}(f(t)-x_0)+2f(t)$$ Putting everything together, $$... 1 Presuming you mean t_n=5t_{n-1}+6t_{n-2} you substitute in t_n=ax^n and you will get x^2=5x+6 I don't know what the =0s are doing there. If they are real, you have t_n=0 and are already done 1 As mentioned in the comments, there is no way to find a defining formula for a infinite sequence from a finite initial segment because given any finite list there are infinitely many ways to extend it. That said, if you know ahead of time that the mystery sequence is defined by some recurrence and you know something about the structure of that recurrence, ... 1 Let's look at the coefficients. We have 2n, n^2+1, and -(n+1)^2 = -n^2 - 2n - 1. Do you notice anything particular about these three terms? Does that lead to the needed particular solution? 1 My first impulse would be to note that$$\frac{T(n)}n=\frac{T(n/2)}{n/2}+\frac1{\log n},$$and that to be able to iterate this requires to look at the powers of 2, since the new sequence$$S(k)=\frac{T(2^k)}{2^k}$$solves the recursion$$S(k)=S(k-1)+\frac1{k\log 2},$$from which I readily see that$$S(k)=S(0)+\frac1{\log ...

Only top voted, non community-wiki answers of a minimum length are eligible