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

learn more… | top users | synonyms

1
vote
1answer
16 views

What does it mean for a reccurence relation to be homogeneous?

I've seen definitions (such as the one here) that state Homogeneous: All the terms have the same exponent. but others (such as this one) claim that if the equation $a_n=\alpha_1 a_{n-1}+\alpha_2 ...
3
votes
2answers
60 views

Does $E^2 \; ( E \approx 1.2640847\ldots)$ equal $D \approx 1.5979102\ldots$?

Does $E^2=D$? Where $E$ is a constant used in the closed form of the Sylvester Sequence (see: Closed form formula and asymptotics) and $D$ is a constant for the closed formula of the sequence A007018 ...
4
votes
1answer
75 views

Generating a recurrence relation

Suppose you have a large collections of red 1x2 tiles, blue 1x2 tiles and green 1x2 tiles. For $n\ge 0$, let $t_n$ be the number of ways to use these to exactly cover the squares of a 2xn checkerboard ...
4
votes
2answers
50 views

Generating a recurrence relation question

A switching game has $n$ switches, all initially in the OFF position. In order to be able to flip the $ith$ switch, the $(i-1)st$ switch must be ON, and all earlier switches OFF. The first switch can ...
1
vote
1answer
56 views

How to find algebraic simplification for recurrence relation with closed-form solution, specifically for the Lucas-Lehmer primality test

I have a question based on the section Proof of correctness in the article Lucas-Lehmer primality test, see following link. ...
0
votes
1answer
110 views

Does solving a recurrence relation by iteration have two different meanings?

I've seen iteration used by plugging numbers in and not simplifying and guessing the explicit formula, e.g., $t_n$ plug $n=1,2,3,4$ in and guess the explicit formula. The other way I've seen is ...
1
vote
2answers
47 views

Solve the recursion $a_n=\frac{1}{4}2^{n-1}-1+3a_{n-1}$

Solve the recursion $a_n=\frac{1}{4}2^{n-1}-1+3a_{n-1}$ I'd know how to solve it if it weren't for that -1. Because of it, I can't divide the particular equation with $2^{n-2}$ to solve it. What can ...
0
votes
1answer
98 views

Particular solution of a non-homogenous recurrence relation

I need some help with the following non-homogenous recurrence relation. $$a_n-2a_{n-1}+a_{n-2}=n+1$$ $$a_0=0, a_1=1$$ When I solve the associated homogenous equation I use the auxiliary equation ...
0
votes
1answer
117 views

Limit of a fraction of double factorials

How can we show that $\begin{align*} \lim_{n\rightarrow\infty} U_n = 0 \end{align*}$ where $\begin{align*} U_n = \frac{(n-1)!!}{n!!}=\frac{n-1}{n}\frac{n-3}{n-2}\frac{n-5}{n-4}\cdots \end{align*}$ ...
0
votes
1answer
55 views

Recurrence relation - repeated substitution

I am having some trouble with solving a recurrence relation with repeated substitutions. $$a_n = 3\cdot2^{n-1}-a_{n-1}$$ I show some work: $$a_n = 3\cdot2^{n-1} ...
9
votes
2answers
428 views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
0
votes
2answers
85 views

Recursive formula to the number of words length n with restrictions

Looking for recursive formula to the number of words length $n$ with the letters $A,B,C $and the following restrictions: neither $AB$ nor $CA$ can occur as a string in the word. I tried to build a ...
1
vote
2answers
42 views

Proving recurrence

I'm trying to prove the following recurrence: $g(n) = 3g(n-1) + 2$ $g(0) = 0$ $g(1) = 2$ $g(2) = 8$ ... I know that $g(n)$ in closed form is equal to $n^3 -1$, but I'm having a hard time proving ...
0
votes
2answers
42 views

Sum of second order recurrence relation, non constant coëfficients

Is there a general way to calculate the sum of a second order recurrence relation with non constant coëfficients? In my case, I have $$N_i = A_iN_{i-1} + B_iN_{i-2}.$$ Where I'm particularly ...
0
votes
0answers
36 views

limit of a recursive sequence, Am I allowed to divide by $b_n^2$?

$$b_1 > 0$$ $${b_{n + 1}} = {{{b_n}^2 + 1} \over {{b_n}}} = {{{{{b_n}^2} \over {{b_n}^2}} + {1 \over {{b_n}^2}}} \over {{{{b_n}} \over {{b_n}^2}}}}\mathop = {{1 + {1 \over {{b_n}^2}}} \over {{1 ...
0
votes
1answer
30 views

Finding general solutions to recurrences

What is the general solution to the recurrence $$x_{n+2} = x_{n+1} + x_n + n-1$$ for $n\ge 1$ with $x_1 = 0$, $x_2=1$? I am stuck on this a bit. Can someone help me understand this?
4
votes
1answer
414 views

Concrete Mathematics - Towers of Hanoi Recurrence Relation

I've decided to dive in Concrete Mathematics despite only doing a couple of years of undergraduate maths many years ago. I'm looking to work through all the material whilst plugging gaps in my ...
-4
votes
1answer
41 views

Closed form expression for the following sequence

I have come across a sequence and am wondering if anyone knows of a closed form expression for it. I am a bit too lazy to figure it out on my own seeing as it is such a minor part of what I am doing. ...
1
vote
3answers
77 views

recurrence relation for squares of fibonacci numbers

I have a problem finding a proof that the squares of the Fibonacci numbers satisfy the recurrence relation $a_{n+3} - 2*a_{n+2} - 2*a_{n+1} + a_n = 0$ and solving this recurrence relation. Some help ...
0
votes
0answers
31 views

Understanding the difference between two similar looking recurrences.

Looking at this recurrence, $f(n) = f(n/2) + nlgn$ The book claims we can conclude that $f(n) = \Omega(nlgn)$ since $f(n/2)>0$. Furthermore, for a sufficiently large $n: lgn \le n^{\epsilon}$ for ...
4
votes
1answer
112 views

Recurrence $a_n = \sum_{k=1}^{n-1}a^2_{k}, a_1=1$

This seems like a really straightforward recurrence. I wrote out the first few terms: $1,1,2,6,42,1806$... It seems to grow faster than $n!$ but slower than $n^n$. Any suggestions about the closed ...
0
votes
2answers
41 views

Algorithm Analysis on Recurrence Relation.

Consider the following recurrenc relation: $f(n) = f(n/2) +nlogn$ Since this does not honor the form of the Master Recurrence, we need to obtain an estimate of the asymptotic order of $f$. According ...
1
vote
1answer
109 views

A self-convolution formula that counts bracket expressions

Problem: Consider an alphabet of size $m+2$, consisting of the two bracket symbols $\ [ \ ] \ $ plus $m$ non-bracket symbols ($m \ge 0$). Define $f_m(n)$ to be the number of length-$n$ strings on this ...
1
vote
1answer
48 views

Function with invariant area under curve

I'm trying to find a function $f$ that fulfills the following property: The area under the curve starting at some point $x_0$ with a width of $x_0$ should always be the same for all $x_0$. In other ...
0
votes
0answers
26 views

Probability, that player $A$ will win the $k$'th round.

Two guys are playing a simple game, guy $A$ has $k$ \$ and guy $B$ has $n-k$ \$. Player $A$ wins with probability $p$. What's the probability, that player $A$ will win the $k$'th round of the bout? ...
0
votes
1answer
40 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...
3
votes
1answer
23 views

Probability, that when we send a $0$ down the network we will get back a $0$

We can send a $0$ or a $1$ over a network of $1,2...$ nodes. Unfortunately on each node with probability $p$ the message is not made different, and with probability $1-p$ the message is XOR'ed. Find ...
1
vote
1answer
363 views

Combinatorics recurrence relation - n digit ternary sequences (non homogenous)

I had a combinatorics problem that I was hoping someone could help with: Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any ...
1
vote
1answer
238 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
0
votes
2answers
34 views

Number of ways to arrange n identical stones into piles

Given, there are n stones which are identical. How many ways can the stones be arranged into piles. Suppose if n=4 , we can make one pile with 4 stones or 2 piles with 3,1 or 2,2 or 3 piles with 1,1,2 ...
2
votes
1answer
85 views

number of derangements

In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses. A derangement of n numbers is a ...
0
votes
2answers
50 views

Limit of a recursively defined sequence

$ a_{n+1} = \frac{3+2a_n}{3+a_n} $ and $ a_0 = 1 $ This sequence is obviously increasing, so if we could prove it is bounded, we'd also prove it converges and we could easily find the limit by $ L = ...
2
votes
1answer
52 views

How to solve this specific recurrence relation

I'm trying to solve the following recurrence relation for $\alpha_j$, for which Mathematica is not helpful. $$ \lambda\alpha_j + (j+1)\alpha_{j+1} = \sum_{\mu = ...
1
vote
1answer
316 views

Combinatorics - Recurrence relation with n letter sequences

I had a particular question about a recurrence relation: Find a recurrence relation for the number of $n$-letter sequences using the letters $A, B, C$ such that any $A$ not in the last position of ...
2
votes
1answer
42 views

recurrence relation

It was some time ago I studied recurrence relations and I came across this one that I cannot solve: $a_{n+3}=-3a_{n+2}+4a_{n}$ with $a_{0}=2$ and $a_{1}=-5$ Ansatz: $a_{n}=r^{0}$ then I get ...
0
votes
2answers
32 views

How to solve this recurrence?

$ E_{n}=2E_{n-1}+ 2^{n-1} $ Can anyone help me to solve this recurrence? Is there a general way to think about recurrence?
2
votes
1answer
348 views

Recurrence relation and ternary sequences

I had a question that I need some help on: Find and solve a recurrence relation for the number of n-digit ternary sequences with no consecutive digits being equal As I worked this out, I ...
0
votes
1answer
36 views

Find a closed form solution of the recurrence f(a, b) = f(a, b-1) + f(a-1, b-1) with base cases f(0, 0) = 1, f(k, 0) = 1, f(0, k) = 0 (k>0).

I made a matrix for the values of a and b and tried to compute $f(a,b)$. I observed that $f(a,b)=2^b$ for b $\le$ a. But for a given value of a($\gt 1$), $f(a,b)$ seems to follow a strange progression ...
2
votes
4answers
114 views

Recurrence sequence limit

I would like to find the limit of $$ \begin{cases} a_1=\dfrac3{4} ,\, & \\ a_{n+1}=a_{n}\dfrac{n^2+2n}{n^2+2n+1}, & n \ge 1 \end{cases} $$ I tried to use this - $\lim ...
6
votes
2answers
111 views

$a_1=1,a_{n+1}=\frac{n}{a_n}+\frac{a_n}{n}$. Prove that for $n\ge4$, $\lfloor{a_n^2}\rfloor=n$

Define a sequence $\left\lbrace a_{n}\right\rbrace$ by $\displaystyle{a_{1} = 1\,,\ a_{n + 1} = {n \over a_n} + {a_n \over n}.\quad}$ Prove that for $n \geq 4,\,\,\left\lfloor ...
1
vote
3answers
58 views

What is $a_5$, given the recurrence $a_{n+1}=a_n+2a_{n-1}$ and we know that $a_0 = 4, a_2 =13$

I am having a very hard time figuring this out. So far I have been able to do the following: Writing the recurrence as a characteristic polynomial = $x^2-x-2=0$ so there are roots, $x=2, x=-1$. So ...
1
vote
1answer
728 views

Legendre polynomials recurrence relation

How can i get? $$P_{n+1}=xP_n(x)-\frac{1-x^2}{n+1} P'_n(x)$$ $n>=0$ Also know as the leadder equation of the legendre polinomials i tried to use de recurrence relations as: ...
1
vote
1answer
58 views

Recursive Sequence Proof

Take the function defined by $a_n= 3n + 1$, for all $n \in \mathbb{N} \geq 0$. Show that this sequence satisfies the recurrence relation $ a_k = a_{k-1} + 3$ $\forall k \in \mathbb{Z}, k \geq 1$. My ...
2
votes
2answers
394 views

Nonhomogeneous Recurrence Relations

Solve the nonhomogeneous recurrence relation $$h_{n}=3h_{n-1}-2$$ $$n\geq 1$$ $$h_{0}=1$$ I have been told to approach this type of problem using two steps. First, solve the corresponding ...
1
vote
0answers
45 views

How to derive recursive equation for expected discounted utility function?

I am trying to mathematically represent expected discounted utilities when the length of a lifetime is uncertain. $V_0$ is the expected discounted utility at $t=0$ and can be represented as such: ...
0
votes
1answer
99 views

Find a recurrent relation and generating function for the sequence

Let An be the nn matrix which has 1's on the leading diagonal and on the diagonals immediatle above and below the leading diagonal. Let an = det(An). Find a recurrent relation and generating ...
0
votes
2answers
34 views

Show Time $T(n) = Θ(n^3)$

I have to show that : $$T(n) = Θ({n^3})$$ We have this recursive function : $$T(n) = 8T(n/2) + n^2, n>=2$$ also we know that $$T(1) = 1$$ And it says that there is a "replacement method" to ...
2
votes
0answers
45 views

(limit of) a linear second order recurrence relation with variable coefficients

I have the following recurrence relation: $(n + 1) a_{n + 2} = (w (n + 1) - c) a_{n + 1} - z (n + 1)*a_{n}$ that I would like to either solve, or to get the $n$ goes to Infinity limit of the ratio ...
1
vote
1answer
85 views

Generating Function via Recurrence Relation

I am trying to find the solution to the following recurrence for polynomials: \begin{align*} h^{[0]}(z) &= z \\ h^{[n+1]}(z) &= z h^{[n]}(z) (z+z^2+...+z^{n+1}) +z \end{align*} I calculated ...
2
votes
1answer
106 views

If $ x_{1} := 1 $ and $ x_{n + 1} := x_{n} + \dfrac{n}{(x_{1} \times \cdots \times x_{n})^{1/n}} $, then $ \dfrac{x_{n}}{\ln(n)} \to \infty $.

Define a sequence $ (x_{n})_{n \in \mathbb{N}} $ of positive real numbers by $$ x_{1} := 1 \quad \text{and} \quad \forall n \in \mathbb{N}: \quad x_{n + 1} := x_{n} + \frac{n}{(x_{1} \times \cdots ...