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

learn more… | top users | synonyms (2)

2
votes
2answers
95 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
30 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
20 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
15 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
20 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
27 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
37 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
32 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
26 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
77 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
18 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 ...
10
votes
2answers
327 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
81 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
144 views

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
50 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
29 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
1answer
121 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
18 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
49 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
129 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) = ...
1
vote
2answers
37 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
32 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
34 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
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
40 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
26 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
48 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
17 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
69 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
62 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
27 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
20 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
103 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 ...
2
votes
3answers
51 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
38 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
31 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
54 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
15 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
40 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
42 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} + ...
5
votes
2answers
228 views

Method of solving no-homogeneous recurrence equation

I need to obtain a closed form of $M(t)$, satisfying the following recurrence equation: $$M(t+1)=a+bM(t)+\frac{c}{t+1}\sum_{t'=0}^tM(t')+df(t)$$ Where $f(t)$ is a known function and $a$, $b$, $c$ ...
1
vote
0answers
49 views

partial fraction (with factoring involved) in recurrence relation problem

i want to factor the denominator of the function $f(x)=4-23x+21x^2/(1-2x-3x^2)(1-3x)$ so that it takes the form $(1-ax)(1-bx)(1-3x)$. What I've got is $4-23x+21x^2/(1-3x)(1+x)(1-3x)$ but the ...
0
votes
1answer
43 views

Recurrence Relation of n-digit quaternary?

Determine the n-digit quaternary (0,1,2,3) sequences in which there is never a 3 anywhere to the right of a zero. So I know that the answer is $a_{n+1}$ = $3a_{n}$ + $3^n$. I understand why it is ...
1
vote
2answers
76 views

Solve recurrence relation using generating function

I'm trying to solve: $a_{n+1}-a_n=n^2$, $n\le0$ , $a_0=1$ using generating functions. Step 1) Multiply by $x^{n+1}$ $$a_{n+1}x^{n+1}-a_nx^{n+1}=n^2x^{n+1}$$ Step 2) Take the infinite sums ...
3
votes
2answers
127 views

Find a Generating Function for Ordered Rooted Ternary Trees

The Full Question If we let $T=$ the family of rooted ternary trees, $t_n =$ be number of trees in $T$ with $n$ nodes and $T(x) = \sum\limits_{n=0}^{\infty}w_nx^n$ be the generating function of $T$. ...
0
votes
2answers
40 views

Why this method of solving recurrence relation works?

Could anyone explain why we can solve recurrence relations by finding the soltuion of its characteristic equation? I'm talking about the method presented here. Is the proof of the method validity so ...
3
votes
3answers
64 views

Sum with many troubles [duplicate]

I am currently considering a sum $$\sum_{r=0}^{n}{\binom{n}{r} (-1)^{r} (1-\frac{r}{n})^{n}}$$ but have no thoughtful ideas how to start. Maybe it's worth noticing that ...
0
votes
0answers
19 views

Solving a recurrence asymptotically.

How can one solve the following recurrence asymptotically - that is, how can one find an explicit function $f(n)$ such that $T(n) = \Theta(f(n))$? $T(n) = \begin{cases} \Theta(1) & \text{if ...
1
vote
2answers
104 views

Solve $a_{n+1} - a_n = n^2$ using generating functions

The Full Question Using the method of generating functions, solve $a_{n+1} - a_n = n^2$ where $a_0 = 1$ My Research Scanned the website for similar answers, reviewed the following links: Solve the ...
0
votes
1answer
32 views

Fibonacci numbers with even index

$a_{0}=1, a_{n}=a_{n-1}+2a_{n-2}+\ldots+na_{n-n}$ We can see that $a_{n}=\sum_{m=0}^{n}{ma_{n-m}}$. Then $G(z)=1+\sum_{n=1}^\infty (\sum_{m=0}^n{ma_{n-m}) \cdot z^n = ...