0
votes
2answers
16 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
18 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
7 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
1answer
36 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
76 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 ...
2
votes
5answers
643 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 ...
1
vote
1answer
42 views

Find the generating function for a series , given a recurrence relation

I am solving a problem on an Online Judge. The problems solution boils down to find the solutions to the following recurrence relation: ...
-1
votes
1answer
25 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
-2
votes
2answers
83 views

Using generation functions solve the following difference equation

Using generation functions solve the following difference equation $$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$
1
vote
2answers
62 views

Get the Nth term of a sequence 1,2,4,7,13,24…

I have a sequence: 1,2,4,7,13,24,44,81, ... and I think it's like a Fibonacci sequence, however you add three number together and not two ("Tribonacci"?). So: $$ v_n = v_{n-1} + v_{n-2} + v_{n-3} $$ ...
2
votes
2answers
25 views

Recurrence relation practice problem that I can't figure out

Thanks for taking the time to look at this problem. I'm trying to prepare for a test on Monday by doing some extra odd numbered problems from my textbook. I'm having a lot of trouble trying to solve ...
0
votes
2answers
42 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
40 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
0
votes
1answer
20 views

Find a sequence $a$ so that $a_n = s \Delta a_n $.

Let $s$ be a real number $ s \ne 0 $. Find a sequence $a$ so that $a_n = s \Delta a_n $ and $a_0 = 1$. Any help with this question will be great. This is my first time doing recurrence relations ...
0
votes
2answers
45 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
0answers
25 views

Need help with recurrence relations in general as well as specific problem

I am supposed to find the unique solution for a recurrence relation and I literally have no idea what to do. Here is what the professor did for us in class: \begin{align*} 3a_{n+1} - 4a_n &= 0 ...
0
votes
2answers
28 views

Solving a Linear Recurrence Relation

I made quick progress on this, and then of course got stumped, so here's the problem: $$a_0 = -1, a_1 = -2, a_n = 4a_{n-1} - 3a_{n-2}$$ So, following the way I was taught to solve this type of ...
3
votes
2answers
71 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
0
votes
2answers
29 views

How to get the characteristic equation from a recurrence relation of this form?

I've been getting the characteristic equation from relations of the form $$U_n=3U_{n-1}-U_{n-3}$$ Thanks to this question I made before: How to get the characteristic equation? Now, I recently ...
2
votes
3answers
33 views

How to Find Recurrence Relation?

I'd appreciate help in understanding how to approach/find a recurrence relation. For example, if we are given the following situation, how would one find a recurrence relation? A computer system ...
2
votes
5answers
60 views

How to find first five terms of sequence?

I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$ I ...
0
votes
2answers
36 views

Solving for Recurrence Function

I was reading the following http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf notes on recurrence relation, page 2. A recurrence function for the Tower of Hanoi is given by ...
2
votes
1answer
55 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
0
votes
2answers
27 views

Proofs by strong induction [duplicate]

I am trying to solve the following problem using strong induction, the problem is the following: For any positive integer $n$, let $T_n$ be the number $1$ if $n<4$ and the number $T_{n − 1} ...
0
votes
0answers
17 views

proving a recurrence relation

I'm trying to prove that the recurrence $T(n) = T(\alpha n)+T((1-\alpha)n)+n$, where $0<\alpha<\frac{1}{2}$, has an order of growth $T(n)= an$ log $n$ $\in \Theta(nlog(n))$ where $a$ is a ...
1
vote
0answers
30 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...
1
vote
2answers
39 views

Find a recurrence for in , the number of integer compositions of n which only have 1s and 2s as parts.

Find a recurrence for $$i_n$$ the number of integer compositions of $n$ which only have $1$s and $2$s as parts. How do you approach this problem?
0
votes
0answers
27 views

Finding general solution to a non-linear discrete time recurrence relation

I am faced to a non-linear discrete time reccurence relation and I can't find the general solution. The first question is: Is there a general recipe for finding the general solution to non-linear ...
3
votes
2answers
77 views

Is there a closed-form solution to this recurrence?

A friend and I were examining polynomials of the form $p_n (x) = x (x+1) (x+2) \cdots (x+n -1)$ and we were trying to come up with some kind of closed form for the coefficients when the polynomial is ...
0
votes
1answer
21 views

Finding the recurrence relation? [duplicate]

If I let $n \geq 1$ be an integer and use a $2 \times n$ board $D_n$ containing $2n$ cells, each side has a length of 1. T The brick can be vetical or horizontal containg $2$ cells(explained in the ...
0
votes
1answer
34 views

Solving a Recurrence Relation

In my research, I encountered the following recurrence relation: \begin{align} g(t) &= (\beta-1) \; g(t-1) + \beta \; f(t)\\ f(t) &=\min\{f(t-1)+g(t-1), \, c \cdot \lambda^t \} \end{align} ...
2
votes
3answers
87 views

How to tackle a recurrence that contains the sum of all previous elements?

Say I have the following recurrence: $$T(n) = n + T\left(\frac{n}{2}\right) + n + T\left(\frac{n}{4}\right) + n + T\left(\frac{n}{8}\right) + \cdots +n + T\left(\frac{n}{n}\right) $$ where $n = ...
0
votes
1answer
60 views

Prove that the recurrence is true [duplicate]

I am working on an assignment question, and am having trouble moving ahead. The question is as follows: Let the total number of bit strings with three consecutive zeros be $t_n$. Prove for $n \ge ...
1
vote
1answer
61 views

Creating Recurrence

If I have an integer $n \geq1$, and I had to draw $n$ straight lines, so that no two of them are parallel as well as no three of them intersect in one single point. These lines divide the plane into ...
0
votes
1answer
48 views

Master Theorem Question

I need to solve the following: $T(n)=T(n-1)+8$ I've tried doing $a=1$, $b=-1$, and $d=8$ but $\log_{-1}1$ doesn't make sense. Any suggestions?
0
votes
1answer
112 views

Solving a recurrence involving floor and square root (Concrete Mathematics 3.28)

I'm working through Concrete Mathematics and having trouble understanding an answer to a problem (as well as what I could've done to come up with the answer). Problem 3.28 asks: Solve the recurrence ...
3
votes
1answer
25 views

Analyzing $n_{i+1} = n_i - n_i^{3/4}$

I have a non-linear recurrence given by $$n_0 = N \\ n_{i+1} = n_i - n_i^{3/4}$$ Are there any techniques to solve this for an exact closed form? Or in lieu of that, an asymptotic estimation? I'm ...
2
votes
5answers
83 views

Finding a recurrence relation in combinatorics

First, my English is not that good so please don't laugh. I need to find a recurrence relation for : The number of words with the length of n that could be composed from the letters A,B,C,D, so the ...
4
votes
2answers
117 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
0
votes
3answers
130 views

Difficult recursion problem

A student can do the things bellow: a. Do his homework in 2 days b. Write a poem in 2 days c. Go on a trip for 2 days d. Study for exams for 1 day e. Play pc games for 1 day A schedule of n days ...
0
votes
1answer
44 views

Generating Function of a Recurrence Relation.

Given a sequence a(n) = a(n -2) , a(0) = 2 , a(1) = -1 Find the generating function What i have done so far: The recurrence relation is going to be a(n) - a(n-2) = 0 A = the generating function A ...
1
vote
2answers
61 views

proof with recurrence relation

How can we proof that number ternary strings that do not contain two consecutive 0s or 1s is $a_n = 2a_{n-1} + a_{n-2}$ What I tried so far: Let $a_n$ be the number ternary strings that do not ...
0
votes
1answer
56 views

recurrence relation related problems

I'm having some difficulties of finding the recurrence relations of; number of divisions of internal region of n sided polygon number of paths from one point to another point in an NxN grid Can ...
1
vote
0answers
268 views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
1
vote
1answer
120 views

Recurrence relations question

A vending machine dispensing books of stamps accepts only one-dollar coins, $1 bills, and $5 bills. a) Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, ...
0
votes
3answers
91 views

Solve the recurrence $ T_{n + 1} = T_{n} + nT_{n - 1}$

Solve the recurrence $$ T_{n + 1} = T_{n} + nT_{n - 1}\,, \quad\mbox{for}\quad n \geq 1\quad \mbox{with initial conditions}\ T_{0} = T_{1} = 1 $$ by finding the exponential generating function and ...
4
votes
2answers
774 views

Recurrence relation for number of bit strings of length n that contain two consecutive 1s

I'm pulling my hair out over a review question for my final tomorrow. Find a recurrence relation (and its initial conditions) for the number of bit strings of length n that contain two consecutive ...
1
vote
2answers
156 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
0
votes
1answer
27 views

I need to use RSolve in mathematica to solve recurrence relations [closed]

I need to use the RSolve command in mathematica to solve recurrence relations and then find a9. I looked at documentations and try for about 2 hours no matter what my answer is not coming out right. ...
1
vote
1answer
102 views

Devise recurrence formula for restricted strings over alphabet $\left\{0,1,2\right\}$.

Let $A_n$ denote set of strings over characters $\left\{0,1,2\right\}$ of length $n$ which do not contain substring $22$. Moreover let $B_n$ denote set of strings which both do not contain ...