# Tagged Questions

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

1answer
185 views

### Finding ($2012$th term of the sequence) $\pmod {2012}$

Let $a_n$ be a sequence given by formula: $a_1=1\\a_2=2012\\a_{n+2}=a_{n+1}+a_{n}$ find the value: $a_{2012}\pmod{2012}$ So, in fact, we have to find the value of ...
1answer
242 views

### Why do the Fibonacci numbers recycle these formulas?

The Fibonacci numbers $F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots$ obey the following recurrence relations, \$ \begin{aligned} &F_{n}-\;F_{n-1}-F_{n-2} = 0\\[1.5mm] &F_{n-1}^3-F_{n}^3-F_{n+1}^3 = ...
0answers
103 views

### A recurrence relation

Motivated by a specific example, I have a rather general question to ask: suppose $a_n$ is a sequence defined by the relation $a_{n+1}=f_na_n+g_na_{n-1}$, $a_0=a>0$, $a_1=b>0$, where both $f_n$, ...
2answers
1k views

### Why is solving non-linear recurrence relations “hopeless”?

I came across a non-linear recurrence relation I want to solve, and most of the places I look for help will say things like "it's hopeless to solve non-linear recurrence relations in general." Is ...
3answers
916 views

### What is the upper bound on $T(n) = 3T(n/2) + n$?

The upper bound on $T(n) = 3T(n/2) + n$ is: $O(n \lg n)$ $O(n \lg 3)$ $O(n^2)$ $O(n \lg n + n)$
3answers
70 views

### Capacity of a discrete channel in the telegraphy case

I'm reading Shannon's article A Mathematical Theory of Communication, and I'm stuck at the telegraphy case example, on page 4. Shannon writes a formula involving $N(t)$, the number of sequences of ...
0answers
125 views

### Solving two-parameter linear recurrence with different initial values

I'm looking for a method to solve the well-known recurrence ralation with different initial values. The one-parameter linear recurrence is easier. Let's take a peek: $a_0 = \alpha$; $a_1 = \beta$; ...
1answer
106 views

### Solve the recurrence: $Q_0=\alpha$; $Q_1=\beta$; $Q_n=(1+Q_{n-1})/Q_{n-2}$, for $n>1$.

This one is from "Concrete Mathematics": Solve the recurrence: $Q_0=\alpha$; $Q_1=\beta$; $Q_n=(1+Q_{n-1})/Q_{n-2}$, for $n>1$. Assume that $Q_n \neq 0$ for all $n \geq 0$. I ...
1answer
196 views

### Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than \$2^n - ...
0answers
97 views

### How to solve the recursive relation in Kalman filter?

I was wondering how to solve the Kalman filter's recursive equation (also see the appendix at the end of this post) for the estimated state $\hat{\textbf{x}}_{n|n}$ at time $n$, over discrete times ...
1answer
354 views

### Interesting Recurrence Relation $T(n) = T(\sqrt{n}) + T(n-\sqrt{n}) + n$

I found an interesting recurrence that I do not know how to solve. I think this has to do with quicksort with pivots at rank $\sqrt{n}$. I do not know how to approach this problem nor found any ...
3answers
108 views

### How do you go about solving difference equations?

Say you have something of the form $p_1 = p$ $p_n=kp_{n-1}+(1-k)(1-p_{n-1})$ How does one go about finding $p_{n}$ in terms of $n,p$ and $k$? In my notes here's how it's found \$p_n-1/2 = ...
1answer
62 views

### Recurrence of Log function

I have the equation $T(n) = 4T(n/2) + n + log(n)$ for $n\ge2$. I am considering the case where $n=2^k$ I have come to the conclusion that $T(n)$ follows the following formula: \begin{align*}T(n) ...
1answer
29 views

### Recurrence & Rate of Growth

I have the equation $T(n) = T(n-2) + n^5 + n$ for $n\ge2$. I want to write $n$ in the form of $bk+r$. Thus $n=2k+r$ where $0\le r<2$, i.e. $r=0$ or $r=1$. I have come to the conclusion that ...
0answers
51 views

### Bivariate recurrence relation

Consider the following recurrence relation: $$A(h,0)=1\\ A(h,h)=c^h\\ A(h,r)=A(h-1,r)+(c-1)\cdot A(h-1,r-1).$$ Obviously, this is just a generalization of A008949, where $c=2$. Since I'm pretty sure ...
1answer
314 views

### Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements

I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it ...
3answers
84 views

### What is  the method to compute $\binom{n}{r}$ in a recursive manner?

How do you solve this? Find out which recurrence relation involving $\dbinom{n}{r}$ is valid, and thus prove that we can compute $\dbinom{n}{r}$ in a recursive manner. I appreciate any help. ...
1answer
177 views

### Line in a proof on p69 in Cassel's Local Fields

I'm trying to read the proof of LEMMA 6.1 (Nagell) Let $u_n$ be defined by $u_0=0$, $u_1=1$ and $u_n=u_{n-1}-2u_{n-2} \hspace{20pt} (n\geq 2)$. Then $u_n=\pm1$ only for \$n=1,2,3, ...
2answers
168 views

### Find recursive formula for definite integral

Let $\displaystyle I_n(x)=\int_{0}^{x}\frac{1}{(t^2+1)^n}\mbox{d}t$ for $n\in\mathbb{N}$. Find recursive formula for $I_n(x)$ that do not need integrals. I don't know how to do such things and I have ...
1answer
183 views

### Non-linear Recursion

I'm trying to prove (or disprove and improve if possible) that the sequence $a_{n+1}=\frac{a_n^2+1}{2}$, where $a_0$ is an odd number greater than 1 contains an infinite number of primes. However, I ...
3answers
393 views

### Solving a difficult recursion via generating functions

I have been trying to solve the recurrence: \begin{align*} a_{n+1}=\frac{2(n+1)a_n+5((n+1)!)}{3}, \end{align*} where $a_0=5$, via generating functions with little success. My progress until now is ...
1answer
88 views

### solving a recurrence

given the general recurrence equation $a_{n+1}-a_{n}=f(n)a_{n+2}$ (1) is this possible to find a function $g(x)$ so $g(x)= \sum_{n=0}^{\infty}a_{n}x^{n}$ ?? where the $a_{n}$ are the solutions of ...
3answers
1k views

### Master Theorem for Solving $T(n) = T(\sqrt n) + \Theta(\lg\lg n)$

I'm trying to solve the recurrence relation: $$T(n) = T(\sqrt n) + \Theta(\lg \lg n)$$ My first step was to let $m = \lg n$, making the above: $$T(2^m) = T(2^{m\cdot 1/2}) + \Theta(\lg m)$$ If ...
2answers
190 views

### Determining a recurrence relation (Homework)

Let ${d_n}$ be the number of DNA strings of length n that contain a pair of consecutive nucleotides of the same type. There are four symbols used in strings of DNA: A, C, G, T. The nucleotides are ...
1answer
170 views

### discrete math recurrence

Im confused as to what the question is asking and how to solve this? Consider the following recurrence: $a_n = a_{n-1} - a_{n-2}$ where $a_0 = 0$ and $a_1 = 1$ (a) Using the recurrence and the ...
0answers
113 views

### What are the recurrence relations used in the relaxed Menage problem?

The relaxed Menage problem: What is number of ways that you can seat n couples around a circular table so that no one is next to their partner? I think I understand the process used in this link to ...
1answer
84 views

### Finding previous term in sequence

I'm afraid this problem fits more to stackoverflow, but maybe it fits also here. For a given $F_n$ (but we don't know $n$) find $F_{n-1}$, knowing that $\forall_{n>1}F_n=F_{n-1}+F_{n-2}$. Also ...
1answer
408 views

### Linear homogeneous recurrence relation with constant coefficients: How does one determine the solution set?

According to my textbook and this Wikipedia article, a recurrence relation of the form $$b_0 a_n + b_1 a_{n-1} + \cdots + b_k a_{n-k} = 0$$ (EDIT: where $b_0 \neq 0$) has the following set of ...
2answers
579 views

### Recurrence $T(n)=T(n/2)+2^n$ and $T(n)=T(n/2+\sqrt n)+\sqrt{6044}$  , without (!) the master method

Given the Recurrences $$T(n)=T(n/2)+2^n$$ and $$T(n)=T(n/2+\sqrt n)+\sqrt{6044}$$ Remark : $T(n)=1$ for $n\le 3$ I'm trying to find their upper bound & lower bound , which is probably $O(2^n)$ ...
1answer
104 views

### Recursive functions and Gamma functions

How do we solve recursive functions using gamma function? Basically I'm not able to understand the connection between the two. I found following reduction while reading on web ...
1answer
221 views

### Recurrence Relation with cosine

is it possible to find general solution of the recurrence relation such as $a_{n}=a_{n-1}+A\centerdot \cos(a_{n-1})$ where $a_{0}=0$ and $A \ll 1$ EDIT: At least for \$a_{n}=a_{n-1}+A - ...
1answer
64 views

### Will this recurrence yield $(4,2,0)$?

Consider the recurrence $$(a,b,c)\mapsto \left(\frac{3a+4b}{5}, \frac{4a-3b}{5}, c\right)$$ and suppose that we start with $(2,3,2)$, and allow swapping positions before applying the recurrence again. ...
2answers
422 views

### Linear homogeneous recurrence relations with repeated roots; motivation behind looking for solutions of the form $nx^n$?

If we have a linear homogeneous recurrence relation, such as $t_{k+1}=4t_k-4t_{k-1}$, and attempt to find solutions of the form $t_n=x^n$ for some $x \in \mathbb{R} \setminus \{0\}$, we obtain the ...
1answer
162 views

### Combinatorial interpretation of Delannoy numbers formula

The Delannoy number $D(a,b)$ can be defined as the numbers of paths on $\mathbb Z^2$ from $(0,0)$ to $(a,b)$ using only steps $(0,1)$, $(1,0)$ and $(1,1)$. It is straightforward to see that they ...
2answers
331 views

### solve recurrence relation $a(n)=2a(n-1)+1$ [duplicate]

Possible Duplicate: Solving a Recurrence Relation/Equation, is there more than 1 way to solve this? I am trying to solve following recurrence relation $$a(n)=2a(n-1)+1\;.$$ I have divided ...
1answer
901 views

### Give a recursive definition for the set of polynomials with integer coefficients.

I'm thinking of the form $$p_n = a_0t^0 + a_1t^1 + a_2t^2 +\cdots + a_nt^n.$$ However the only way I can think to write it is $$p_n = p_{n-1}+ a_nt^n.$$ I'm probably thinking the wrong way. This ...
2answers
805 views

### Recurrence $T(n)=T(\sqrt n) + \Theta(\log(\log(n))$

I need to find the bounds of the above recurrence . I've tried the following however got stuck : $T(n)=T(\sqrt{n})+Θ(\log(\log(n) )=$ $n=2^m,\quad m=\log(n)$ \$T(2^m)=T(\sqrt{2}^m ...
0answers
119 views

### Recurrence relation for the digits of the integer square root in binary

I was investigating a question on the Electrical Engineering Stack Exchange site, available here: ...
3answers
839 views

### What is the bound of :   $T(n)=T(n-2)+\log(n)$?

Given : $T(n)=T(n-2)+\log(n)$ I need to find the bound for the above recurrence . So: \begin{align*} T(n-2)&=T(n-2-2)+\log(n-2)\\ &=T(n-4)+\log(n-2)\\ T(n)&=T(n-2)+\log(n)\\ ...
1answer
3k views

### Recurrence relation for number of ternary strings that contain two consecutive zeros

The question is: Find a recurrence relation for number of ternary strings of length n that contain two consecutive zeros. I know for ternary strings with length one, there are 0. For a length of 2, ...
3answers
167 views

### Recurrence relations problem help

okay im supposed to find a recurrence relation for $$a_{n+1}= b \cdot a_n + c \cdot n \ \ \ \ \ \ \ \ \ \ \ \ \mathbf{(1)}$$ where $b$ and $c$ are constants. the method we learned in class was ...
1answer
74 views

### number of ways to form a specific number with n digits

I'm trying to find the number of ways to form a number with certain properties. The number has following properties. The first digit is always 1. The $n$th digit can take values from 1 to k+1 ...
3answers
264 views

### Notation for factorial-type pattern with a skip/step of two instead of one?

I came across a peculiar pattern when solving a recurrence relation today: Some sequence $a_n$ looks as such: $a_0 = 1$ $a_2 = \frac{1}{2 \cdot 1}$ $a_4 = \frac{1}{4 \cdot 2 \cdot 1}$ \$a_6 = ...
0answers
61 views

### Construction of polynomials with non-commutative elements.

I have a simple set of polynomials which I know how to construct for each integer $n$, but I havn't been able to write them down in terms of concrete sums and products. For $n\in\mathbb N_+$, we have ...
2answers
306 views

### How to approach 2-Dimensional Recurrence Relations

How to solve the following 2-dimensional recurrence relation? Let $n, n'$ be natural numbers $> 0.$ Let $r$ be a positive integer $\ge 0.$  P(n+n',r) = \sum_{i=0}^{r} P(n, ...
1answer
364 views

### generating matrix for a recurrence relation

for the recurrence f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4) , how can one get the generating matrix so that it can be solved by matrix exponentiation? For ...
2answers
688 views

### Recurrence $T(n)=2T([n/2]+17)+n$ and induction.

Show that the solution to $$T(n) = 2T\left(\biggl\lfloor \frac n 2 \biggr\rfloor+17\right)+n$$ is $\Theta(n \log n)$? So the induction hypothesis is  T \left( \frac n 2 \right) = c\cdot \frac n2 ...
3answers
80 views

### sequence $U_k=a_0U_{k-1}+a_1U_{k-2}+\cdots+a_{k-1}U_0$

Is there a general formula for $U_k$ defined by $$U_k=a_0U_{k-1}+a_1U_{k-2}+\cdots+a_{k-1}U_0$$ where the $a_i$ are in arithmetic progression and $U_0=1$? Do there always exist $c,d$ such that ...
1answer
102 views

### “Non-commutative” Recurrence relation $C_m = \alpha_m C_{m-1} + \beta_m C_{m-2}$

I have a problem, which is probably quite trivial. Consider a recurrence relation of the form $$C_m = \alpha_m C_{m-1} + \beta_m C_{m-2},$$ where the coefficients $\alpha_m$ and $\beta_m$ are ...
1answer
111 views

### Explicit formula for sequence with parity-based recursion

How do we find an explicit formula for the sequence $(a_i)_{i=1}^\infty$ in terms of $a_1=C$ if a_{i+1}=\begin{cases} a_i-13 & i \text{ even}, \\ 2a_i & i \text{ odd}.\end{cases}\quad i\ge2 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 141, "mathjax_display_tex": 14, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.918218195438385, "perplexity_flag": "head"}