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

learn more… | top users | synonyms (2)

0
votes
0answers
30 views

How to compute linear recurrence of a sum of binomial-multiplied linear recurrences [duplicate]

I have $$g(n) = \sum_{k=1}^{n} \binom{n}{k}f(k)$$ where $f(k)$ is a large linear recurrence. $g(n)$ is also a linear recurrence as well. Normally, when computing the value of a linear recurrence, I ...
1
vote
1answer
17 views

Problem with nonhomogeneous recurrence relations

I studying Discrete maths during this semester and I need your help. I have been trying to solve one non-homogeneous recurrence relation and read many-many guides how to do this, but I haven't found ...
4
votes
1answer
55 views

Simplying linear recurrence sum with binomials

Is there a way to simplify $$\sum_{k=1}^{n} \binom{n}{k}f(k)$$ Where $f(k)$ is a large linear recurrence?
4
votes
1answer
64 views

Dynamical system $x_{n+1} = \frac{1}{2}(x_n - \frac{1}{x_n}) \ \ , \ \ n = 0, 1 , 2,…$

Consider the dynamical system $$ x_{n+1} = \frac{1}{2}(x_n - \frac{1}{x_n}) \ \ , \ \ n = 0, 1 , 2,... $$ So by using the substitution $x_n = \cot(y_n)$, I have found: $$ x_n = \cot(\cot^{-1} ...
1
vote
1answer
43 views

Solving Log equation using master theorem

I`m studying Master Theorem, and I got stuck in the case 3. The example is : T(n) = 3T(n/4) + nlogn. I have no idea how my teacher got the final value, c = 3/4, based on the equation below : 3*[n/4 ...
0
votes
2answers
42 views

Solve the following recurence relation.

While I was working on some graph theory problem I encounter the following recurrence relation $$a_{n+1}=a_{n-1}+6$$ where $a_0=3.$ Note: I have rewritten the recurrence relation as recommended.
0
votes
1answer
37 views

Recurrence relation of $T(n) = T(n^\frac13) + \log n$

I'm having trouble deciphering what this recurrence relation is: $$T(n) = T(n^\frac13) + \log n$$ when I try to expand it out I get: $T(n) = T(n^\frac1{3^k}) + k\times\log n $ my problem is ...
1
vote
2answers
43 views

Solve recurrence relation - t(n)=(n-1)*t(n-1) [closed]

How can I solve the following recursive relation: t(n)=(n-1)*t(n-1) where the base case is t(1)=1 Is it okay just saying ...
2
votes
2answers
73 views

Proving an expression is perfect square

I have this expression I got in one larger exercise: $$\frac{(2+\sqrt3)^{2n+1}+(2-\sqrt3)^{2n+1}-4}{6}\frac{(2+\sqrt3)^{2(n+1)+1}+(2-\sqrt3)^{2(n+1)+1}-4}{6}+1$$ and i need to prove it is perfect ...
0
votes
2answers
28 views

Sequence of numbers recurrence relation

A sequence of real numbers $$ u_1, u_2, u_3... $$ satisfies $$u_1=1$$ and the recurrence relation $$4u_{n+1}=au_n-2$$ for all positive integers n where a is a real constant. Express $$u_n$$ in terrms ...
1
vote
1answer
19 views

How can I find the sum of any homogenous linear recurrence relation?

I've become interested in linear recurrence relations of the form $a_n=-a_{n-1}-a_{n-2}- ... $ where $a_0=1$. For the first of these relations I considered $a_n=-a_{n-1}-a_{n-2}$ where $a_0=1$ and ...
0
votes
1answer
14 views

Reccurence for the numbers of the strip partition

Let's consider a partition of a strip $ 3 \times n$ into $1 \times 2$ rectangles and call $a_{n}$ - the number of such partitions. For instance, $a_{0}=1, a_{1}=0, a_{2}=3, a_{3}=0 \ldots$. How to ...
1
vote
0answers
16 views

Recurring Folds Through A Circle

If I were to cut a circular disk of paper, I would have a disk with one section. If I were then to fold it through its centre, I would have a disk with two sections (divided by the crease). If I were ...
1
vote
1answer
20 views

How to solve the delay algebraic equation $xf(x) + \alpha f(x - {x_0}) - \alpha f(x + {x_0}) = 0$?

In the process of solving a problem, I am faced with the problem of finding a non-zero function $f:\mathbb{R} \to \mathbb{R}$ which satisfies the equation $$xf(x) + \alpha f(x - {x_0}) - \alpha f(x + ...
1
vote
1answer
32 views

Closed form of recurrence equation

I am solving warm up problem 1.2 from Concrete Mathematics book. I've got the right answer by induction: $$ f(0) = 0\\ f(n) = 3f(n-1) + 2, $$ But I can not figure how to simplify it to the closed ...
0
votes
2answers
30 views

Prove that two recursive sequences are always not zero.

I have the following recursive sequences: $x_n = x_{n-1} + 2y_{n-1} , x_1 = 1$ $y_n = y_{n-1} - x_{n-1}, y_1 = -1$ where $ x_n,y_n \in \mathbb{Z}$ I have to show that for any $n$ neither $x_n$ ...
0
votes
0answers
20 views

Solving a linear recurrence with a multiplicity of two

I was given this problem and I am trying to figure out where I go wrong solve the linear recurrence: $f(0) = 0$, $f(1) = 0$, $f(2) = 18$, $f(n) = 3f(n − 1) − 4f(n − 3)$ Here is what I have so ...
0
votes
1answer
62 views

Find a function F(n) that satisfies the recurrence

i am stuck with this problem Find a function F(n) that satisfies the recurrence F(n) = 2F(sqrt(n)) + 1 for all n ∈ N Please help me...
0
votes
1answer
17 views

Recurrence Relation with Strings

Q. How many strings in {0,1,2,3} have an even number of 1's. The answer provided uses the recurrence relation $a_{n+1} = 3a_n + (4^n - a_n)$. The hint given was that consider the last string of ...
9
votes
2answers
271 views

How many permutations of a multiset have a run of length k?

Background $\newcommand\ms[1]{\mathsf #1}\def\msP{\ms P}\def\msS{\ms S}\def\mfS{\mathfrak S}$Suppose I have $n$ marbles of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color ...
0
votes
3answers
71 views

Calculus: Converge of a recursive series?

I'm going crazy to solve this problem: I've a sequence defined by: $$x_1 = 1$$ $$x_2 = 2$$ $$x_{n+2} = \frac{1}{2}(x_{n}+x_{n+1})$$ And I have to prove that this sequence converges and what is its ...
0
votes
1answer
77 views
+50

Result of a $2D$ random walk with position dependent probabilities of step

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk:- A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
1
vote
1answer
42 views

How can find this two sequence recursive relations?

Let $$D_{n}=\sum_{j=0}^{n-1}(-1)^{n+j-1}\dfrac{\binom{2n-4}{j}}{n+j-1},E_{n}=\sum_{j=0}^{n-1}(-1)^{n+j-1}\dfrac{\binom{2n-4}{j}}{n+j}$$ I want find $D_{n}$ and $E_{n}$ recursive relations, I ...
1
vote
2answers
26 views

Simplification of an Equation with Recurrence Relations

I'm reading through examples on this site. In example 2_2, given the recurrence relation $A_n - 2A_{n-1} = 2n^2$, the guess for the particular solution is $A_n= Bn^2 + Cn + D$. Substituting that into ...
2
votes
0answers
46 views

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
1
vote
1answer
17 views

Inequality for recursive-defined values

$f_{n+2} = \frac{6}{5}f_{n+1}-f_{n}, f_0 = 0, f_1 = 1$ I need to prove that $f_n < 5/4$ I found that $f_{n} = \frac{1}{8} i 5^{1-n} \left((3-4 i)^n-(3+4 i)^n\right)$ and spend much time for ...
0
votes
1answer
32 views

I do not understand Recurrence Examples on donald knuth's concrete mathematics last page on chapter 1 [closed]

Example 1: When $n = 100 = (1100100)_2$ our original josephus values $\alpha=1,\beta=-1,\gamma=1$ yield: Answer: $ n = \qquad(1\qquad 1\qquad 0\qquad 0\qquad 1 \qquad 0\qquad 0)_2\quad=\quad 100\\ ...
0
votes
2answers
118 views

Sequences of sums of Pascal's triangle

The sequence $$ 1,3,6,10,16,28,56,120,256,528,1056 $$ is defined in OEIS as "sum of every 4th entry of row n in Pascal's triangle, starting at "n choose 2"". It satisfies the recurrence $$ a(n) = ...
-2
votes
1answer
77 views

2010 local contest questions on recurrence relation?

How we can solve this recurrence relation: $T(n)= 2^{log_{2}3} T(n/2)+ n \sqrt {n} $ anyone could help me this difficult question, that mentioned in 2010 local contest?
1
vote
2answers
34 views

Solving a recurrence relation (textbook question)

$a_{n+1} - a_n = 3n^2 - n$ ;$a_0=3$ I need help for solving the particular solution. Based on a chart in my textbook if you get $n^2$ the particular solution would be $A_2n^2 + A_1n + A_0$ and $n$ ...
0
votes
0answers
31 views

Does this problem have analytic/approximate analytic solution?

Define $F[i]=F[i-1]-F[i-1]^c$ with $F[0]=r>0,c\in(0,1)$. Define $R(r,c)=\min\{i:F[i]<1\}$. What is solution to $c\in(0,1)$ in $R(r,c)=r^{1/k}$ with some given $k>1$?
0
votes
0answers
19 views

Riccati Finite Difference Equation:

Question: Consider the finite difference equation in Zeilberger notation: $$D_{1,x} [y] = a_0(x) + a_1 (x) y + a_2 (x)y^2 $$ Which in functional form is: $$ y(x+1) - y(x) = a_0(x) + a_1 (x) y + ...
-1
votes
2answers
208 views

one recurrence relation with generating function

what is generating function for {$a_n$}$_{n \geq 0} $ sequence that defined by $a_0=0$ and $a_n=\frac{1 \times 5 \times ... \times (4n-3)}{1 \times 2 \times ... \times n}$ $(n \geq 1)$. ...
1
vote
1answer
50 views

$f(n)= \Sigma_{A \subseteq N} \Sigma_{B \subseteq N}$

for positive integer n we have: $N={1,2,...,n}, f(n)= \Sigma_{A \subseteq N} \Sigma_{B \subseteq N} , |A \cap B|$. for example, how I can calculate $f_5$? I have ...
0
votes
0answers
32 views

Fibonacci polynomial summation

The $n^{th}$ value of a polynomial ($S_n$) of order $k$ is a polynomial in $x$ is given by : $\left(\frac{S_n}{x^n}\right)$= $\sum_{j=0}^n \left(\frac{{F_j}^k}{x^j}\right)$ Where ${F_j}$ is the ...
0
votes
1answer
24 views

Formula for weighed geometric sum

I'm trying to find an easy way to derive a formula for: $S_{n} = \frac{1}{n}\sum_{i=0}^{n}(n-i)x^{i}$ I've found a recurrence relationship of sorts: $S_{n+1} = \frac{xnS_{n}+n+1}{n+1} = ...
0
votes
1answer
45 views

If $f(n) = af(n/a) + c \log n$, how does $f(n)$ grow?

Question: If $f(n) = af(n/a) + c \log n$, how does $f(n)$ grow? This is an attempt to correct my answer here: Time Complexity of Recurrence : $f(n)=3f(\frac{n}{3})+O(logn)$? It turns out my answer ...
0
votes
1answer
16 views

Integrality and boundness implies periodicity

Let's consider the reccurence $a_{n+r}=c_{1}a_{n+r-1}+\ldots+c_{r}a_{n}, c_{i}\in \mathbb{Z}$. How to prove that if the $a_{n}$ is integer and bounded, then it's periodic? Could someone suggest the ...
0
votes
0answers
30 views

Strong induction proof problem with $x$-cent postage stamps

I have the following example problem that has to be proven using strong induction: "Prove that every amount of postage of $12$ cents or more can be formed using just $4$-cent and $5$-cent stamps." ...
0
votes
2answers
58 views

recurrence formula for number of decimal numbers with some restrictions

I ran into a Olympiad Question that so difficult, if $a_n$ be the number of decimal numbers with length $n$ that has no $0$ in the digits and also has not any combinations $11,12,21$, I want to find ...
0
votes
1answer
22 views

Proof by induction of recurrence relation

I've been shown the following proof by induction of $P(n)$ where $n$ is a positive integer presumably. This is in the context of algorithmic analysis. $ P(n):T(n) = \begin{cases} ...
1
vote
0answers
17 views

Discrete Model Finding Stability

For the discrete model $$x_{t+1} = (\lambda +1)x_t +x_t^3$$ Draw a bifurcation diagram (expressing the equilibrium vs $\lambda$ for values of $\lambda$ near zero. I have the bifurcation diagram. It ...
0
votes
1answer
33 views

How to make a cobweb diagram

I am struggling making a cobweb diagram for the function $$x_{t+1}=8x_t/{1+2x_t}$$ So I understand when making the cobweb diagram, that I have to draw the line $y=x$ But where I have trouble ...
1
vote
2answers
40 views

Recurrence relations with factors in recurrence

How would I go about approaching solving a recurrence relation such as: $$a_{n}=2a_{\frac{n}{3}}+1$$ I'm just not sure how to get a general form for a non-recursive solution, can someone walk ...
0
votes
1answer
36 views

problem understanding induction proof for following recurrence sequence $\frac{a_{n-1}+a_{n-2}}{2}$

I've got this recurrence sequence and it's proof, but I'm stuck with the 2nd/3rd step in the induction step. $$a_0:=0, a_1:=1\\ a_n:= \frac{a_{n-1}+a_{n-2}}{2}$$ Show that for all $n\in N$: ...
1
vote
1answer
23 views

Finding the moments of normal variables

How to calculate the moments of a normal random variable with mean $\mu$ and variance $\sigma^2$? Using integration by parts we get the recurrence relation (calling $a_n = E(X^n)$) $$\begin{cases} ...
0
votes
1answer
43 views

Given minimal characteristic polynomial how to derive linear recurrence?

I was able to find minimal characteristic polynomial of the sequence of numbers using Berlekamp-Massey algorithm. For example, for a sequence $$ ...
1
vote
1answer
13 views

Recurrence Relation for the number of lattice paths with an even number of N moves

The Full Question Find a recurrence for the number of lattice paths beginning at $(0,0)$ with steps N and W, and which contain an even number of N steps. My Work A string of length $n$ can end in W ...
0
votes
1answer
25 views

Solving a recurrence relation with special cases

I need help solving the following problem with a recurrence relation. A miner is trapped in a mine with three doors. The first door will lead him to safety in two hours. The second door leads ...
0
votes
0answers
27 views

Summation Reduction

Given \begin{align*} a_{0} = a_{1} = \frac{3}{2} \hspace{10mm} m a_{n+2} = a_{n}^{3} + (m-3) a_{n} + 2 \end{align*} then find the value of the series \begin{align} \sum_{n=0}^{\infty} \frac{a_{n} + ...