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

learn more… | top users | synonyms (2)

3
votes
2answers
64 views

Count the number of 10 digit numbers with given condition

PROBLEM: Count the number of 10 digit numbers with digits from $\{1, 2, 3, 4\}$ and no two adjacent digits differing by $1$. I am able to provide a solution using recursion but it is a very ...
1
vote
1answer
35 views

Exponential Generating Function Fun

Given the recurrence relation of $a_n = a_{n-1} + n$, for $n \gt 0$, Where $a_0 = 1$. I know the solution is: $a_n = \frac{1}{2}n^2 + \frac{1}{2}n + 1$. I am not having troubles finding this ...
0
votes
0answers
14 views

Recurrence equation for equivalent (charasteristic) classes in graphs

Is there any Recurrence equation to get the number of equivalent classes in graphs? For example if you have: 2 vertex in a graph there are 2 equivalent classes 3 vertex in a graph there are 4 ...
1
vote
2answers
48 views

Finding the recurrence relation.

So the question has 2 parts to it. Let $f(n)$ be the number of sequences in length n that are built of 0, 1, and 2, so that after zero there's always 1 right after it. Let $g(n)$ be the number of ...
5
votes
2answers
163 views

Is it possible to compute factorials by converting to matrix multiplications?

An $n$-th term of the Fibonacci sequence can be computed by a nice trick by converting the recurrence relation in a matrix form. Then we compute $M^n$ in $O(\log n)$ steps using exponentiation by ...
3
votes
1answer
32 views

How do you solve the recurrence relation $T(n) = cn(dn + T(n-k))$?

How do I come up with a big-O approximation to $T(n) = cn(dn + T(n-k))$ where $c, d \in \Bbb{R}$ are fixed. $T(n)$ is the running time of a recursive algorithm. This seems difficult as usual. :)
1
vote
0answers
66 views

Ternary strings (combinatorics, recurrence)

The questions is: for $A_n$ find all ternary strings of length $n ≥ 0$ that don't include substring $”11”$. Provide answer in form of: a) recurrence relation b) combinatorial expression After that, ...
1
vote
2answers
56 views

Solving $U_{n+1}=(U_{n})^{2} (n+2)$

I need help solving the recurrence relation: $U_{n+1}=(U_{n})^{2} (n+2)$, with $U(1)=2$. I've tried wolfram alpha, but something really horrible came up. The methods I've tried have just failed so I ...
3
votes
0answers
79 views

Permutation and Combinatorics Problem

A function $G$ is defined on a set $S$ with size $k$ : $G(a_1,a_2,a_3,\ldots,a_k)$. $G(a_1,a_2,a_3,\ldots,a_k) = 1$ if and only if a convex polygon can be created by taking these $k$ elements as the ...
2
votes
1answer
44 views

How do you solve this recurrence relation/use it in a sequence to find it's GIF value?

The sequence {$x_k$} is defined by $x_{k+1} = x_k^2 + x_k$ and $x_1=\frac{1}{2}$. Now, if [.] denotes the greatest integer function, then which of the following options is correct: A) $[\frac{1}{x_1 ...
1
vote
1answer
49 views

Finding the reccurence relation from a problem.

let $f(n)$ be the number if ways to lay down tiles in a formation of size 2 x n using tiles of size: $$ \begin{matrix} 1 \\ 1 \\ \end{matrix} $$ and tiles of size: $$ ...
3
votes
0answers
65 views

Solve the Recurrence relation : $a_n= (a_{n-1})^3a_{n-2}$ , $a_0=1, a_1=3$

$a_n= (a_{n-1})^3a_{n-2}$ , $a_0=1, a_1=3$ I'm ask to get an expression for $a_n$. So i tried to solve with induction: ...
1
vote
2answers
300 views

How to find formula for recursive sequence sum?

I have the following sequence: $$a(1) = 1$$ $$a(n) = a(n-1) + n$$ For example: $$a(1) = 1$$ $$a(2) =3$$ $$a(3) =6$$ $$a(4) =10$$ $$a(5) =15$$ $$a(6) = 21$$ Which approach should I use in order to ...
0
votes
1answer
57 views

Find the recurrence relation

Assume that a must course lasts for $2$ hours while both a technical elective course and a free elective course lasts for $1$ hour. Find the recurrence relation for the number of ways to arrange ...
1
vote
1answer
34 views

Solving recurrence relations of n rabbits on island

Okay so one pair of rabbits is left in an island. After 1 month it produces 2 pairs of rabbits, and 2 months or older they produce 6 every month. I came up with the recurrence relation $ A_{n} = ...
1
vote
2answers
98 views

Solve the recurrence relation : $f(n) = 1 + \frac{f(n) + f(n-1) + \cdots + f(1)}{n+1}$

For naturals $n$, $f(n) = 1 + \dfrac{f(n) + f(n-1) + \cdots + f(1)}{n+1}$. What is $f(n)$? This is not a homework problem. Is there a general method to solve these recurrence relations? I will ...
0
votes
0answers
33 views

Deriving difference equation from a rational system function $H(z)$

If I have the system function $H(z)$ of a linear time-invariant system, how do I derive the difference equation relating its input $x(n)$ and output $y(n)$? The system function is given by $$H(z) = ...
0
votes
1answer
21 views

Can somebody explain the steps in this recurrence back substitution problem?

I'm usually good until the first couple of steps, then once you add more and more things I get lost pretty easily. Can somebody give me a step-by-step analysis of this? I'd really appreciate it. ...
0
votes
1answer
25 views

Recurrence relation for binary strings of length $n$ that doesnt contain $010$ pattern?

I've looked up this question in here and found one whose answer didnt look complete to me or maybe I couldnt figure it out correctly.. I can understand the first part of the answer $a_n = a_{n-1} + ...
0
votes
1answer
57 views

Need to solve this recurrence relation

We are provided with a recurrence relation as follows:- $F(n,k) = F(n,k-1) + F(n-k+1,k)$ $F(n,1) = n $ $F(X,k) = 0$ if $ (X\leq0)$ I need help in solving this for k=1 to 10 only Edit:- I have ...
1
vote
1answer
35 views

Time Complexity recurrence

When we have the recurrence $T(N)=T(N-1)+T(N-2)$, one normally uses $x^N$ and solves for $x$ which gives the golden ratio. But why does one use $x^N$ and not something else, like $\log(N)$ or $N$?
2
votes
2answers
41 views

How to use recurrence to define generating function? How to write generating function as power series?

I am a software engineer teaching myself combinatorics. This problem is destroying me, but I am following what I thought was the appropriate strategy to solve a recurrence. I am also confused as to ...
1
vote
0answers
13 views

Waring's Problem and the floor function - solving a recurrence relation by hand

First-time poster here. While doing some research on Waring's problem and the term $\{(3/2)^n\},$ I determined that the following recurrence relation holds for a certain sequence (here $n$ is a fixed, ...
0
votes
1answer
41 views

Find all “steady-state” solutions

The number of individuals in a certain population (in arbitrary real units) obeys, at discrete time intervals, the equation $$y_{n+1} = y_n(2-y_n) \hspace{2 mm}\text{for} \hspace{1 mm} n = ...
7
votes
6answers
121 views

If $a_{n+1}=\frac {a_n^2+5} {a_{n-1}}$ then $a_{n+1}=Sa_n+Ta_{n-1}$ for some $S,T\in \Bbb Z$.

Question Let $$a_{n+1}:=\frac {a_n^2+5} {a_{n-1}},\, a_0=2,a_1=3$$ Prove that there exists integers $S,T$ such that $a_{n+1}=Sa_n+Ta_{n-1}$. Attempt I calculated the first few values of ...
0
votes
4answers
47 views

Finding the $S_n$ of a recursion

$$\sum_{k=0}^{n} (1+2k+4(k(k+1)))=?$$ In order to find the $S_n$ what methods are best fitted for such problem? Is it possible to use the lemma $\sum_{i=0}^{n} i= {n(n+1)}/2$ and plug in? I tried but ...
0
votes
0answers
68 views

Need to evaluate the possible recurrence from the table

In continuation to my question posted yesterday ,I obtained one table on the basis of some initial values, and tried to observe some pattern out of it. \begin{array}{|c|c|c|c|} \hline 0& & ...
0
votes
0answers
32 views

Recurrence Relations:

I have this recurrence relation I'm supposed to do, and I can't seem to figure out the next step: $T_{n} = T_{n-1} + 2n^2, T_{1} = 1$ What I have so far is this: $T_{n} = T_{n-1} + 2n^2$ $T_{n-2} ...
2
votes
1answer
18 views

How to prove the recurrence relation for this generating function problem?

I am a software engineer and I am learning combinatorics theory on my own. I recently got stumped by the following problem. Problem Let $a_{0} = 2$ where $a_{n} = 3a_{n-1} - 2$ with $n>0$. ...
0
votes
2answers
35 views

Finding Recursive Definition for the following:

How would i start off to find a recursive definition for $X_{0}$=.19 $X_{1}$=.1919 $X_{2}$=.191919 ... $X_{n+1}$= what goes here?
1
vote
1answer
40 views

Symmetric random walk: mean duration given absorption occurs at 0

This is exercise 2 from Section 3.9 of Probability and Random Processes by Grimmett and Stirzaker: For a simple random walk $S$ with absorbing barriers at 0 and $N$, let $W$ be the event that the ...
0
votes
2answers
46 views

calculus - limit of recurrent sequence

$a_1>0$ $a_{n+1} = {1\over2}(a_n + {1 \over a_n})$ assume $\lim a_n = A \in \mathbb R - \{0\}$ Can anybody help me solve this? We should first show the limit exists. That should be easiest by ...
0
votes
2answers
26 views

If $y_n = 2x_n-1$, show that $y_{n+1} = y_n + y_{n-1} + 1$

If $y_n = 2x_n-1$, how do you show $y_{n+1} = y_n + y_{n-1} + 1$ with $y_0 = 1$ and $y_1 = 1$? Would you start with $y_{n+1} = y_n + y_{n-1} + 1$, find a formula for $y_n$ and then compare it with ...
0
votes
1answer
21 views

Differential equation associated to a linear difference equation

We have a linear difference equation with constant coefficient $$\begin{cases}x(t+1)=ax(t)+by(t)\\y(t+1)=cx(t)+dy(t)\end{cases}$$ What is the differential equation associated with the above ...
0
votes
0answers
17 views

Explicit formula for quadratic recurrence

Let $x_0 \in \mathbb{C}$ be given and $a, b, c \in \mathbb{C}$ constants. Define the sequence $(x_n) \subset \mathbb{C}$ by the relation $$x_{n+1} = a x_n^2 + b x_n + c$$ Can one find explicit ...
0
votes
1answer
49 views

How do you show $s_n = \frac{x_{n+1}}{x_n}$ where $(x_n)$ is the Fibonacci sequence?

Let $(s_n)$ denote the sequence satisfying: $s_{n+1} = 1 + \frac{1}{s_n}$ with $s_0 = 1$. Let $(x_n)$ denote the Fibonacci sequence and $x_n = \frac{5 + \sqrt{5}}{10}(\frac{1 + \sqrt{5}}{2})^n + ...
2
votes
3answers
57 views

Finding the sum of n terms $S_n$ starting from sigma $k=0$

$$\sum_{k=0}^{n} ((4k-3)\cdot 2^k)+4=(2^{n+3}+4)n-7\cdot2^{n+1}+15$$ How? I've tried everything but i don't see it. Any equivalent solutions are also welcome, thanks.
3
votes
4answers
79 views

Recurrence relation $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$?

Consider the following recurrence relation $T(1)=1$ $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$ for all $n≥1$ The value of $T(m^2)$ for $m≥1$ is $(m/6) (21m – 39) + 4$ $(m/6) (4m^2 – 3m + 5)$ $(m/2) (m^{2.5} – ...
1
vote
1answer
29 views

Why is the recurrence relation for finding the # of bit strings of length n that contains a pair of 2 consecutive 0's…?

$$a_n = a_{n-1} + a_{n-2} + 2^{n-2} \text{ ?}$$ The solution manual states, Let $a_n$ be the number of bit strings of length $n$ containing a pair of consecutive $O$s. In order to construct a bit ...
0
votes
2answers
86 views

Finding the nth term of 1, 6, 24, 76,212,…

What different methods of recursion can I use to find the nth term of this recursion? This should be simple but I don't know what I'm missing. Could you demonstrate the method? $n(0)= 1$, $n(1)= 6$, ...
2
votes
1answer
90 views

Find a recurrence relation and generating function of…

Model the amount of crab being caught per year based on the assumption that the # of crab caught in a year is the average of the # caught in the 3 preceding years. a.) Find a recurrence ...
0
votes
1answer
57 views

formula for the nth term of this sequence?

How do you find a formula for the nth term of this sequence? given that $x_n$$_+$$_1$ = $x_n$ + $x_n$$_-$$_1$ (Fibonacci sequence) and $x_0 = 1$ and $x_1 = 1$. Do i complete the square on $x^2 - x - ...
1
vote
2answers
40 views

How to get the Binet-form for the sequence *[1,5,45,441,4361,…]*?

The sequence $[1,5,45,441,4361,...]_{k\ge 0}$ has a relatively simple recursion formula; I got for the recursion $$a_0=1, \qquad a_1=5, \qquad a_{k+2}= 10 a_{k+1} - 1 a_k - 4 $$ I have also found, ...
2
votes
2answers
58 views

Help me understand this sequence problem

Today, I encountered a problem in "Problem-Solving Strategies" by Arthur Engel (Chapter $9$. Sequences, page-$225$): Prove that there does not exist a monotonically increasing sequence of ...
0
votes
2answers
38 views

Solving recurrence using recurrence trees.

I have a recurrence which I know has the solution $O(\lg n)$, it looks like this: $$T(n) = T(\sqrt n) + \lg n$$ If I understand correctly, the recurrence tree method involves looking for the term ...
1
vote
1answer
47 views

Can reduction formula be applied on $\int \cos^n x \: dx$ when n is a negative integer?

The reduction formula states as: enter image description here for integration of $\cos^n x$: $$ \int \cos^n x \: dx=\frac1n \cos^{n-1} x\sin x+\frac{n-1}n \int \cos^{n-2} x \: dx $$ But if ...
0
votes
1answer
61 views

Find a recurrence relation that counts the number of off-diagonal elements of an $n+1 × n+1$ matrix…

Find a recurrence relation that counts the number of off-diagonal elements of an $n+1 × n+1$ matrix. Solve this recurrence relation for an expression of the number of off diagonal entries as a ...
0
votes
0answers
21 views

What to do if your characteristic equation is not fully reducible over your field when solving a recurrence relation?

My problem is a little more difficult. However, essentially, my problem comes up when we're supposed to find the solution to: $R(n)=R(n-3)+1$, $R(0)=R(1)=R(2)=1$ (the initial conditions don't matter ...
0
votes
1answer
23 views

Solve Non-homogeneous recurrence relations

Solve the recurrence relation $u_n = 2u_{n-1} + 2^n - 1$ where n is greater than or equal to 1 and $u_0=0$. We have characteristic root equal to 2 with multiplicity 1. So homogeneous part will have ...
0
votes
1answer
31 views

How I can solve this difference equation: $(2m+3) w_{m}-(2m+1) w_{m+1}-2m²-4m-1=0$

How I can solve this difference equation: $$(2m+3) w_{m}-(2m+1) w_{m+1}-2m²-4m-1=0$$ I have no idea to start.