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

learn more… | top users | synonyms

1
vote
3answers
116 views

Can Master Theorem be applied on any of these?

1) $T(n) = 6T(n/2) + 2^{3 \log(n)}$ 2) $T(n) = 8T(n/2) + \frac{n^3}{(\log(n))^4}$ 3) $T(n) = 9T(n/3) + n(\log(n))^3$ Can the complexity for these be calculated with the Master Theorem? I am not sure ...
0
votes
1answer
71 views

How to solve a recurrence relation?

I want to solve the following recurrence relation with Guess method and induction: $T(1) = 1$ $T(n) = T(3n/4) + T(n/5 + 1) + n$ for $n > 1$
1
vote
0answers
70 views

What is common between difference operators and recurent relations?

They say that solutions of recurrence relations are combinations of exponential functions, the series like [1 a a^2 a^3 and etc]. I know that the difference operators have a matrix like ...
1
vote
1answer
64 views

Outcome probabilities for set number of dice rolls with conditional extra rolls

If we are allowed $n$ rolls of a dice, where each roll of 1 gives us an extra roll, what is the probability of rolling m 1s in the sequence of available rolls, and likewise what is the probability of ...
1
vote
1answer
24 views

2nd order homogeneous repeated roots

$$a_{n+2}-6a_{n+1}+9a_{n}= 3^n \quad n\geq 0 \quad a_{0}=2 \quad a_{1}=3$$ Got repeated roots of 3, so $a_{n}= A\cdot3^n+b\cdot (n\cdot3^n)$ how would i calculate A+B when there is $3^n$? Edit: So ...
0
votes
2answers
35 views

2nd order homogeneous difference equation

$$a_{n+2} = 9a_{n+1} - 18a_n,\quad n\geq 0,\,\,a_0=1,\,\, a_1=3$$ I got to the point where i moved all to LHS which gives me $a_{n+2} - 9 a_{n+1} + 18 a_n$ (correct me if I'm wrong). I then ...
0
votes
2answers
49 views

Find sequence shch that $a_n^2=\frac{a_{n-1}^2+a_{n+1}^2}{2} (n=2,3,\ldots) $

I would appreciate if somebody could help me with the following problem Q: Suppose $a_n \in \mathbb{N}$ is natural number such that: $$a_n^2=\frac{a_{n-1}^2+a_{n+1}^2}{2} (n=2,3,\ldots), a_1=10 $$ ...
1
vote
1answer
52 views

Finding the explicit formula for the succession $x_0=2, x_{n+1} = 5x_n$ and proving it with induction

I'm trying to learn about recursion, first with this exercise: Find the explicit formula for the succession $$x_0=2, x_{n+1} = 5x_n$$ So, from what I've seen, I should test a bit. I see that the ...
0
votes
0answers
21 views

Proving the characteristic equation

Consider the recurrence relation: $a_n = \alpha_1 a_{n-1}+\alpha_2 a_{n-2}+...+\alpha_k a_{n-k} ,$ where $\alpha_1 , \alpha_2 , ... \alpha_n $ are constants. 1) Prove that if $b$ is a non-zero ...
3
votes
0answers
44 views

Showing that a number is part of sequence A000275 in OEIS

Consider the sequence of integers defined recursively by $c_0 = 1$ and $$ c_p = \sum_{l = 0}^{p-1} (-1)^{p+l+1} \binom{p}{l}^2 c_l $$ for $p \geq 1$. This is sequence A000275 in the online ...
2
votes
1answer
49 views

Justifying onto function properties

For $m,n\ge0$ let $O(m,n)$ be the number of onto functions a) Explain why $O(m,n)=0$ when $m\lt n$ I said: since O is an onto function it implies that for all elements of n there is atleast one m ...
1
vote
4answers
66 views

How to solve this reccurence relation?

Let a,b,c be real numbers. Find the explicit formula for $f_n=af_{n-1}+b$ for $n \ge 1$ and $f_0 = c$ So I rewrote it as $f_n-af_{n-1}-b=0$ which gives the characteristic equation as $x^2-ax-b=0$. ...
3
votes
1answer
35 views

Finding recurrence relation that do not contain GOAL

Find a recurrence relation and initial conditions for $c_n$, the number of sequences of length $n$ of upper case letters that do not contain GOAL.
3
votes
1answer
88 views

Generating and solving recurrence relations

I am trying to do this question but don't know where to go from here: The question: For $n\ge1$ let $t_n$ be the number of ways to tile the squares of a 2xn checkerboard using 1x2(which can be rotated ...
0
votes
1answer
51 views

Solve the Recurrence Relation of $A_{n+1} = A_n+A_{n-1}$ for $n\geq2$

I am trying to solve some recurrences for an exam that I found from a past final: I am given $A_1=1$ and $A_2=3$. I re-wrote the relation as $A_{n+1} - A_n - A_{n-1} =0$ and found the characteristic ...
1
vote
1answer
29 views

Recurrence relation related proof

Find a recurrence relation for the number of ternary string that do not contain 00 or 11 .
0
votes
0answers
34 views

Is crossdirectional partial tetration of order $n^c$?

The following animation shows a sum of a matrix where the parameter $c=0$ gives a straight line in pink, and as $c \rightarrow 1$ it approaches the Chebyshev $\psi$ function, the blue staircase. This ...
1
vote
0answers
40 views

finding a recurrence relation for tile covering problem [duplicate]

for $n \ge 1$ let $t_n$ be the number of ways to.cover the squares of a 2xn xheckerboard using 1x2 tiles which can be rotated (ie 2x1 tile) and 2x2 tiles. 1x2 tile comes in 5 different colors and 2x2 ...
0
votes
0answers
33 views

Can Maple solve recurrence relations when n is only certain numbers?

If you have an equation $a(n)=a_{n-1}+2a_{n-2}$ only defined when n is powers of 2, how would convey that to Maple that n has a restriction? What if you wanted only $n \ge 2$?
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
73 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
55 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
100 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
96 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
113 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
54 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} ...
8
votes
2answers
394 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
83 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
39 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
397 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
76 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
30 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
111 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
40 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
106 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
22 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
353 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
223 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
84 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 ...