Questions regarding functions defined recursively, such as the Fibonacci sequence.
6
votes
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 ...
10
votes
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 = ...
0
votes
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$, ...
4
votes
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 ...
-1
votes
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)$
0
votes
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 ...
2
votes
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$; ...
2
votes
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 ...
4
votes
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 - ...
2
votes
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 ...
0
votes
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 ...
0
votes
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 = ...
2
votes
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) ...
2
votes
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 ...
1
vote
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 ...
2
votes
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 ...
2
votes
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. ...
6
votes
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, ...
0
votes
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 ...
4
votes
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 ...
13
votes
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 ...
3
votes
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 ...
0
votes
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 ...
3
votes
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 ...
-1
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
4
votes
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)$ ...
0
votes
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
...
1
vote
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 - ...
3
votes
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.
...
6
votes
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 ...
2
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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: ...
3
votes
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)\\
...
3
votes
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, ...
3
votes
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 ...
1
vote
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 ...
3
votes
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 = ...
1
vote
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 ...
4
votes
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, ...
1
vote
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 ...
2
votes
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 ...
5
votes
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 ...
0
votes
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 ...
2
votes
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 ...
