# Tagged Questions

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

30 views

### Find a recurrence relation and the Fourier-Legendre Series

Rodrique's Formula for the $n$th Legendre Polynomial is $$P_n\left(x\right)=\dfrac{1}{2^nn!}\dfrac{d^n}{dx^n}\left(\left(x^2-1\right)^n\right)$$ The Fourier-Legendre series of a function f is ...
79 views

### Given $x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3$

I friend told me that apart from trivial ones, the elements in this sequence never equal powers of 3: $$x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3.$$ Could you please help me to prove this?
266 views

### Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$

Consider the following iterative process. We start with a 2-element set $S_0=\{0,1\}$. At $n^{\text{th}}$ step $(n\ge1)$ we take all non-empty subsets of $S_{n-1}$, then for each subset compute the ...
39 views

### Deducing Skolem-Mahler-Lech theorem from a $p$-adic interpolation result.

Let $p$ be a prime number, let $d$ be an integer greater than $1$ and let $f\in\mathbb{Z}_p[X_1,\cdots,X_d]^d$. I have already proved the following $p$-adic interpolation theorem: Theorem 1. (...
21 views

### General and particular solution from recurrence equation

I need to find the General Solution of $S_n = 3S_{n-1}-10$ for n = 1,2,3,4.... then I need to find the particular solution where $S_0 = 15$, then check the particular solution with the original ...
36 views

### How to find limit of the sequence

A sequence is defined by recurrence relation $f_{n+1}=\frac{3}{7}f_n+8$ with $\mu_0=-14$, then what is the limit of the sequence? $14$ $-14$ $\frac{-3}{7}$ $\frac{3}{7}$ My attempt: As wiki : ...
45 views

### asymptotic behavior of functions which are defined recursively

For $x\in[0,1]$, define $f_1(x)=1$ and $$f_{n+1}(x)=(1-x)^n\left(nx+1\right)+f_n(x)\left(1-(1-x)^{n+1}\right)\;\;\mbox{for}\;\;n=1,2,\dots.$$ I want to study some asymptotic results of $f_n$. For ...
232 views

46 views

### Master theorem with $f(n) = n\log(\log n)$

I have a question related to algorithm time complexity and master theorem. How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$? We have 3 cases: I don't know which one to ...
19 views

38 views

### Recurrence relation general solutions [closed]

how would I go about tackling this kind of question? I'm struggling with the concept of recurrence relations. Any advice would be apreciated. Find the general solution of each of the following ...
17 views

### Subsets of an ordered round table of numbers

The problem reads: Let the integers $1,2,\dots,n$ be arranged consecutively around a circle, and let $g(n)$ be the number of ways of choosing a subset, no two consecutive on the circle. In a ...
63 views

### Recurrence relation problems

For some math homework (that was already due but I really want to understand the content) I was asked the following question, How should I go about answering this? I'm new to recurrence relations and ...
44 views

### Radius of convergence from recurrence with variable coefficients

I am solving via power series the ivp $$y'-2xy=0,\quad y(1)=2.$$ The "solution" is $$y(x)=2\left(1+2(x-1)+3(x-1)^2+\frac{10}{3}(x-1)^3+\frac{19}{6}(x-1)^4+\frac{26}{10}(x-1)^5+\cdots\right)$$ with ...
37 views

### 12 numbered pigeonholes and balls [duplicate]

This problem was inspired by this James Randi challenge. Given $12$ numbered ($1$ to $12$) pigeonholes and $12$ numbered balls (also from $1$ to $12$); what is the probability that a random ...
13 views

### Difference equation of Z-Transform

I could not obtain difference equation of Z-Transform which is indicated below: $$H(z) = \frac {1.1202\cdot10^{-6}z^2 + 2.2404\cdot10^{-6}z + 1.1202\cdot 10^{-6}}{z^2 -1.9996z + 0.996}$$ In simple ...
925 views

### How does one solve this recurrence relation? [closed]

We have the following recursive system: $$\begin{cases} & a_{n+1}=-2a_n -4b_n\\ & b_{n+1}=4a_n +6b_n\\ & a_0=1, b_0=0 \end{cases}$$ and the 2005 mid-exam wants me to calculate answer ...
32 views

### Proving a sequence defined by a recurrence relation converges

How can I prove that this iterative sequence converges to $2$? Can I use the convergence definition? $$a_{n+1} = \frac{a_n}{2} + \frac{2}{a_n},\qquad a_0 = 4$$ Thanks for the help.
17 views

### Finding a general form $d_n$ for a recurrence relation

I have the following recurrence relation $$d_n = 2^{(1-2n)/2}d_{n-1},\qquad d_0=1,$$ for $n\in\mathbb{Z}$. Is it possible to find a general form for $n$? After calculating a few numbers around ...
22 views

### best way to find sum of powers of prime factors of a number

What is the best way to find the sum of powers of prime factors of a number? What I did till now is : ...
53 views

### Solution to recurrence relation, as a formula involving summation operator

Here is what I am tasked with.. Find a solution to the recurrence relation: $F(0) = 2$ $F(n+1) = F(n) + 2n^2 - 1$ as a formula involving the summation operator $$\sum_{i=1}^n$$ Sorry for the ...
38 views

### Solving the recurrence $T[n] = \frac{n}{T[n-1]}$

Ive had some experience solving recurrences but i think they have been more simple than this one. This is what i have so far: \begin{array}{rcl}T[1] & = & 1 \\ T[n] & = & \frac{n}{T[...
16 views

26 views

### How to solve this recurrence relation with a summation in it?

How would one go about solving this recurrence relation: $T(n)$=$\sum_{i=1}^{k}T(n - d_i)$ ? For this recurrence relation, $k$ is the number of coin denominations, and $d_i$ is the specific coin ...
Let say i have the following relation - $$T(1) = c1$$ $$T(n) = T(n/2) + n$$ I need to prove by induction that this function is bounded by $O(n)$. I just dont get how to choose $C,N_{0} > 0$ . If ...