# Tagged Questions

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

356 views

### Solving recurrence equation with floor and ceil functions

I have a recurrence equation that would be very easy to solve (without ceil and floor functions) but I can't solve them exactly including floor and ceil. \begin{align} k (1) &= 0\\ k(n) &= n-...
155 views

### How is Ramanujan's recurrence relation for his nested radical solved?

The Wikipedia article, here, describes in some detail the derivation of Ramanujan's famous nested radical, $$\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+\cdots}}}}.$$ In the Wikipedia article it provides a ...
46 views

### Find recursive formula for special function

Kind of a strange question I know, but here goes: We are given a string of letters $T$ without any gaps or commas, just letters. Depending on what $T$ is, it could be broken down to form a valid ...
45 views

### Solving recurrence relation with repeating roots

I am aiming to solve this recurrence relation and I have chosen the Characteristic Equation method: $d_n = 4(d_{n-1}-d_{n-2})$ with $d_0 =1, d_1=1$ Finding the C.E. I get: $x^2-4x+4=0$ Solving for ...
73 views

### Examine the convergence of a sequence $\{a_{n}\}$ which is given by $a_{1}=a>0,a_{2}=b>0, a_{n+2}=\sqrt{a_{n+1}a_{n}},n\ge 1$

I used inequality between arithmetic and geometric means to show that a sequence $\{a_{n}\}$ is bounded: $$a_{n+2}=\sqrt{a_{n+1}a_{n}}\le \frac{a_{n+1}+a_{n}}{2}$$ Solving this, I get quadratic ...
127 views

### How do I solve the recurrence relation without manually counting?

Given the recurrence relation : $a_{n+1} - a_n = 2n + 3$ , how would I solve this? I have attempted this question, but I did not get the answer given in the answer key. First I found the general ...
86 views

### What is wrong with my solution for the recurrence $T(n)=2T(\sqrt{n})+\lg\lg n$?

an someone explain where did I do a mistake? Solve the recurrence relation $$T(n)=2T(\sqrt{n})+\lg\lg n$$ Let$$\lg n = m$$ $$S(m) = 2S(m/2)+\lg m$$ We know (proved in class) that $$S(m) = O(m \lg m)$$...
160 views

### Recurrence relation of number of groups of matching parenthesis

I was trying to solve this problem: How many ways can N pairs of parenthesis form K matching groups? By 'a group of matching parenthesis' I mean a sequence of matching parenthesis which can not be ...
222 views

42 views

99 views

### Strong Mathematical Induction: Prove $3\mid b_n$ for a given recurrence relation $b_n$

Here is what I have so far: Proof $3\mid b_n$ for $n$ integers $\geq 1$ Base Cases both given $b_1=3, b_2=9$ and $b_n=6b_{n-2}+b_{n-1}$ $$P(1)=3\mid b_1$$ $$P(1)= 3\mid 3$$ Since $3\mid 3$, the ...
176 views

### Given $g(x)$, how to solve function recurrence $f(x)=af(\alpha x)+bf(\beta x)+g(x)$ where $\alpha\neq\beta$

If we have a recurrence like $$f(x)=af(\alpha x)+bf(\beta x)+g(x)$$ where $a,b,\alpha,\beta\in\mathbb{R}$ and $\alpha\neq\beta$ and $g(x)$ is known. How can we solve this kind of recurrence? For ...
154 views

38 views

### Solving Recurrence Relations using Iteration

$$a_0 = 2; \qquad a_k=4a_{k-1}+5 ~ \forall\ k\ge 1$$ I have already tried solving for $a_1$ through $a_5$.
105 views

### Derive a closed formula for the generating function of this recurrence relation

This is a given recurrence relation $a_n=19(F_0a_{n-1}+F_1a_{n-2}+...+F_{n-1}a_0)$ where $F_n$ is Fibonacci number and $a_0=9$. Find the generating function $A(x)$ of the sequence $a_n$ I get the ...
136 views

Call the following a NON additive-subtractive prime sequence or lets name it Gary's sequence. It goes like this: let a(0)=2. The next term is defined as smallest prime number which cannot be expressed ...