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

learn more… | top users | synonyms

5
votes
3answers
234 views

The number of length-n ternary sequences with even ones and even zeroes

Just starting to appreciate recurrence relations Let $T_n = $ number of length-n ternary sequences with an even number of ones and an even number of zeroes. $T_0 = 1$, because $0$ is an even number, ...
0
votes
1answer
31 views

Why does $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$ imply $T(n)=\mathcal{O} (n\log(n))$

I am learning about sort algorithms and their complexities. For merge sort, I'm confronted with $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$. The author makes the claim with no ...
4
votes
1answer
99 views

Is there a generating function for $\sqrt{n}$?

I tried to come up with a closed form for the ordinary generating function for the sequence $\{\sqrt{n}\}_0^{\infty}$ but I could not. Is there a way to derive it using the recurrence relation ...
0
votes
0answers
23 views

Inhomogenous Recurrence Relation: Looks correct?

I'm working on the problem below currently. I feel that I am doing everything correctly, but I just have this tiny problem that's causing me issues! I've attached my working out below. As ...
3
votes
4answers
225 views

Solving Recurrence equation

I have a problem with this type of recurrence equation. Find the solution of recurrence equation: $$T(1)=2,$$ $$T(n+1)=T(n)+2n , \quad \forall n\geq 1$$ Indeed, I tired to Solving Recurrences ...
1
vote
2answers
99 views

How many $a$-nary sequences of length $b$ never have $c$ consecutive occurrences of a digit?

Let $S(a,b,c): = \#\{a$-nary sequences of length $b$ without $c$ consecutive occurrences of a digit$\}$. For example, $S(2,n,3)$ would be the number of binary sequences of length $n$ without $3$ ...
0
votes
1answer
27 views

math notation of iterated function

I'm trying to determine the proper notation for the following loop I have written in computer code: Set x = 2 set y = 3 For z=1 to z=5 (increasing the value of z by 1 each ...
1
vote
1answer
108 views

Number of n-digit ternary sequences with an even number of 0's and 1's

Can someone help me derive a recurrence relation to find the number of n-digit ternary sequences with an even number of 0's and 1's? I know that you need to break it down into cases where the ...
2
votes
1answer
62 views

Number of ways to derive the number 14 using a recursive definition of EVEN numbers?

I have the following recursive definition for the construction of EVEN Numbers- [RULE 1]: 2 is an EVEN number. [RULE 2]: If x is an EVEN number and y is an EVEN number, then x+y is also an EVEN ...
2
votes
2answers
117 views

Non homogeneous Recurrence relation problem

So here i have this non homogeneous recurrence relation i need to solve: $$a_{n}=12a_{n-2}+16a_{n-3}+9\cdot 4^{n}+81n,$$ where $a_{0}=0$, $a_{1}=1$ $a_{2}=98$. I'm confused at the homogeneous ...
5
votes
0answers
38 views

Finding a recurrence relation for a sequence not containing $0$ in the digits. Also showing $\sum\limits_{k=1}^n \dfrac{1}{a_k} < 90$

Let $1,2,3,4,5,6,7,8,9,11,12,\ldots$ be the sequence of all positive integers which do not contain the digit zero. Write $\{a_n\}$ for this sequence. By comparing with a geometric series, show that ...
0
votes
2answers
25 views

Is it a solution of the recurrence relation?

I am given a recurrence relation such that $a_n = 2a_{n-1} - a_{n-2}$ for $n = 2, 3, 4...$ I am to test whether $a_n = 2^n$ is a solution to the recurrence relation. I am new to this, but it seems ...
1
vote
1answer
74 views

Need help with recurrence relation

So the question is: "Find a recurrence relation for the number of ways to pick $n$ objects from $k$ types with at most 3 of any one type" I think I figured out what it would be excluding the last ...
0
votes
1answer
121 views

find the recurrence relation (homework)

I'm new to recurrence relations and I'm having trouble figuring out this problem: Find a recurrence relation for the number of ways to make a stack of green, yellow, and orange napkins so that no two ...
0
votes
1answer
29 views

Going from recurrence relations to closed form

How do I go from the following recurrence relation a(n) = (n+1)a(n-1) where a(0) = 2 to a closed form? I know I need to use an iterative approach but I am not ...
1
vote
0answers
37 views

Infinitely many primes in second-order recurrence

I just wondered about the following question: Suppose that we are given a homogeneous second-order recurrence relation, $x_{n+2}+ax_{n+1}+bx_n=0$ for all $n\in\mathbb{N}$. Can we choose integers ...
3
votes
2answers
98 views

Proving integrality of a sequence of numbers

How would one go about proving whether or not the terms of a sequence such as the following $$1, 1, 1, 1, 1, 6, 21, 181, 5221, 1090981, 986241401, 51490676208426,\ldots$$ defined by ...
3
votes
1answer
80 views

UNBEATABLE recurrence relation

Hi I don't know where to start to solve this reccurence relation: $g(1)=2$ $ g(2n)=3g(n)+1$ $ g(2n+1)=3g(n)-2$ of coures I can make it: $ g(1)=2$ $ g(n)=g(2n)/3-1/3$ $ ...
1
vote
1answer
41 views

Solve the following recursive relation by using generating functions

$a_n - 9a_{n-1} + 26a_{n-2} - 24a_{n-3} = 0, n \ge 3, a_0 = 0, a_1 = 1,a_2 = 10$ I have tried solving it by the normal way, but I have no idea how to solve it by generating functions. Please give me ...
1
vote
2answers
60 views

Find the generating function?

How can I find a generating function for the following mathematical term? $$ a_r = \left(\matrix{2r \\ r}\right) $$ Is it the $\dfrac{r!}{2r(2r-r)!} = \dfrac{(2r-1)\cdot(2r-2)\cdot\ldots\cdot ...
1
vote
2answers
38 views

How can I find a recursive relation for the following words?

if $d(n)$ is the number of words created by the alphabet $\{a,b,c\}$ of length $n$ that do not contain $abc$ term then write a recursive relation for $d(n)$. I have read the same questions but there ...
2
votes
1answer
40 views

How can I find a recursive relation for the following words?

if c(n) is the number of words created by the alphabet {a,b,c} with n length that the word does not contain 'ab' term then write a recursive relation for c(n). I don't have enough knowledge of the ...
2
votes
2answers
40 views

Find suitable recurrence relation

So I need to find a correct recurrence relation to this problem: How many series of size n over {0,1,2} exist, so that each digit never appears alone. For example, this series is good: 000110022, and ...
1
vote
1answer
35 views

set problem of integers

Consider the following set $F=\{F^0, F^1, F^2, \ldots\}$. This set consists of positive integers which satisfy the following properties: $F^0= F^1=1$ AND $F^n= F^{n-1} + F^{n-2}$ for all positive ...
0
votes
0answers
24 views

recursive relation in rational expression form

I am looking for a closed form expression for the variables $n_i$ that are stationary solutions of the recursive relation: $ n_i(t+1)=n_i(t)\sum_mf_{i,m}\frac{K_m}{\sum_j f_{j,m}n_j(t)}$ i.e. the ...
0
votes
1answer
29 views

Relation between coefficients of Maclaurin series and recurrence relations

Suppose $I_{2n}=\int_0^{\pi}x\sin^{2n}x \;dx$. Then one can obtain the following: $$I_0= \frac{\pi ^2}{2}, I_1= \frac{\pi ^2}{4}, I_2= \frac{3\pi ^2}{16}, I_3= \frac{5\pi ^2}{32},\ldots, I_n= ...
0
votes
2answers
63 views

Recurrence for number of strings of length n without consecutive vowels

Someone asked almost the same question recently, but I'm having a ton of trouble trying to calculate the rest of the problem.
1
vote
2answers
66 views

How can I get the following recursive relation that explained?

if $b(n)$ is the number of words created by the alphabet ${a,b,c}$ with $n$ length that each word has at least one $a$ character and after each $a$ there is no $c$ character write a recursive relation ...
7
votes
1answer
305 views

How to prove this sequence of inequalities

The number $c_{g}(n)$ is defined by the recurrence \begin{equation} c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) , \end{equation} with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$. ...
0
votes
2answers
30 views

Find $f(n)$ when $n = 2^k$ where $f$ satisfies the recurrence relation $f(n) = f\left(\frac{n}{2}\right) + 1$ with $f(1) = 1$

Given: $f(1) = 1$. Answer: $$f(2) = f(1) + 1 = 1 + 1$$ $$\ldots$$ $$f(4) = f(2) + 1 = 1 + 1 + 1.$$ How do I find the value of $f(n)$ where $n$ is an odd integer? Let say $f(3) = ...
2
votes
2answers
180 views

Finding the recurrence relation for number of ways to deposit n dollars

Question: A vending machine dispensing books of stamps accepts only one dollar coins, 1 dollar bills and 5 dollar bills. a) Find a recurrence relation for the number of ways to deposit n dollars in ...
0
votes
1answer
19 views

Recurrence formulae help

I need help with the following recurrence problem. Suppose we have a vector with n integers $\langle x_1,x_2,\ldots,x_n\rangle$. For this vector we calculate the relative parts of the even numbers and ...
0
votes
1answer
12 views

How does one find annihilators for recurrence relations?

I've recently taken an interest in the Method of Annihilators for solving recurrence relations. However, I taught myself using nearly solely this Power Point presentation. Thus, my knowledge is ...
0
votes
0answers
38 views

Solution of Recurrence Relation for 1/2-integers

Suppose one wants to solve a recurrence relation of the form $$ c(m+1) - c(m)/f(m) = -g(m) $$ for $c(m)$. The general solution can be given by $$ c(m) = ...
1
vote
3answers
102 views

non-homogeneous recurrence relations

The question is: $a_{n}=12a_{n-2}+16a_{n-3}+9\cdot 4^{n}+81n$with $a_{0}=0 ,a_{1}=1 ,a_{2}=98$ I tried to deal with the particular solution first by: ...
1
vote
4answers
47 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
0
votes
1answer
83 views

Induction Proof of: Find $f(n)$ when $n=2^k$, where $f$ satisfies the recurrence relation $f(n)=f(\frac{n}2)+1$ with $f(1)=1$

How can I proof this using regular induction and strong induction? $$f(2^k)=f(\frac{2^k}2)+1=f(2^{k-1})+1$$ $$f(2^{1-1})=f(2^0)=f(1)=1$$ $$f(2^{2-1})=f(2^1)=f(2)=f(1)+1=2$$ ...
3
votes
4answers
206 views

Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$

$g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ With initial conditions $g_{0} = 23, g_{1} = 37, g_{2} = 42 $ This is a practice question I'm working on, and I'm running into absurd amounts of ...
0
votes
1answer
35 views

solution for recurrence relation, characteristic roots method.

For my characteristic roots method for solving a homogeneous recurrence relation, I got the roots for the equation as $2,2,3,3$. for satisfying the boundary conditions, will the general solution be ...
1
vote
2answers
70 views

Recurrence relation with generating function problem

I've got a recurrence problem that I'm close to solving, but having trouble with finishing up. Solve the following recurrence relation using generating functions: $$g_n = g_{n-1} + g_{n-2} + ...
0
votes
1answer
18 views

How should I find the analytical form of these recursive equations

I have $$x_1(t+1) = (1-m \rho_1)x_1(t) + n\rho_2 x_2(t) + h1$$ $$x_2(t+1) = (1-m \rho_2)x_2(t) + n\rho_1 x_1(t) + h2$$ Suppose $x_1(0)$ and $x_2(0)$ are known. How can I find the analytical form of ...
0
votes
2answers
41 views

Domain and range transformation

How can I solve this recurrence relation using Domain and Range transformations: $$ \begin{array}{rcl} n^2 a_n &=& 5(n-1)^2 a_{n-1} +2 \\ a_0 &=& 0 \\ \end{array} $$
-1
votes
1answer
48 views

How should I proceed to solve this recurrence relation: $T(n) = T(n - 1)^2$

I tried to solve this recurrence relation, but I was confused when I had to determine the pattern. $$ T(n) = \begin{cases} 3, & \text{if }n = 0 \\ T(n - 1)^2, & \text{if }n > 0 \end{cases} ...
2
votes
2answers
44 views

Maximum of a function from integers to integers

Suppose $f$ is a function form positive integers to positive integers satisfying $f(1)=1$, $f(2n)=f(n)$, and $f(2n+1)=f(2n)+1$ for all positive integers $n$. Job: Find the maximum of $f(n)$ when $n$ ...
0
votes
1answer
28 views

Recurrence relations :rate of growth

Consider the multiplication of bacteria in a controlled environment. Let ar denote the number of bacteria there are on the r-th day. We denote the rate of growth on the r-th day to be ar- 2(ar- 1). If ...
2
votes
5answers
686 views

Explanation of recursive function

Given is a function $f(n)$ with: $f(0) = 0$ $f(1) = 1$ $f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$ I was wondering if there's also a non-recursive way to describe the same function. WolframAlpha tells ...
2
votes
3answers
108 views

Proof by induction of a recursive sequence

I am studying CIE A levels Further Maths and I am stuck at a question from June 2002: Q The sequence of positive numbers $u_1,u_2,u_3,...$ is such that $u_1<4$ and ...
0
votes
0answers
23 views

Find solution to recursion relation

Consider a following recursion relation: \begin{equation} a_s^{(m+1)} = s a_s^{(m)} 1_{s \le m} + a_{s-1}^{(m)} 1_{s\ge 2} \end{equation} for $s=1,\dots,m+1$ subject to $a^{(1)}_1= 1$. The solution ...
2
votes
1answer
37 views

Solving a recurrence realtion using forward substitution.

I have to find $T(n) = 7 \cdot T\left(\frac{n}{7} \right)$ for $n>1$ when $n$ a power of $7$. So far I have: $$T(7) = 7\cdot T\left(\frac{7}{7}\right) = 7 \cdot T(1) = 7.$$ Then, $$T(49) = 49 ...
1
vote
3answers
50 views

Where is the error in finding the particular solution to this recurrence relation?

The question is to write the general solution for this recurrence relation: $y_{k+2} - 4y_{k+1} + 3y_{k} = -4k$. I first solved the homogeneous equation $y_{k+2} - 4y_{k+1} + 3y_{k} = 0$, by writing ...