0
votes
3answers
35 views

Figuring out the steps in a Recursive Function

I have the following recursive function: $f(0) = 7$ $f(n+1) = f(n) + 6n + 1$ for all integers $n => 0 $ I know the answer is $f(n) = 3n^2 + 2n + 7$ I would like to know the steps to get to this ...
0
votes
3answers
103 views

Strong Induction and Recursion

Consider the recursion given by \begin{equation}f(n) = 2f(n−1)− f(n−2)+6 \text{ for } n ≥ 2 \text{ with } f (0) = 2 \text{ and }f (1) = 4 \end{equation} Use mathematical induction to prove that ...
1
vote
2answers
81 views

Recursive formula for tiling checkerboard

The question asks to find a recursive formula for $t(n)$ where $t(n)$ denotes the number of tilings a $2\times n$ checkerboard using only $1\times 1$ tiles and $L$-tiles (formed by removing the upper ...
14
votes
1answer
222 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemples. How to calculate the number of circuits that ...
0
votes
1answer
41 views

Recurrence relation that skips $n-1$?

A difficult question I'm having problems with regarding recurrence relations and recurrence equations. The question is as follows: In how many different ways can I cover a 3xn checkberboard with 2x1 ...
0
votes
1answer
40 views

Combinatorics recursion question. [closed]

How many binary vectors of length n do not contain a sequence '001' ? Solve by recursion and explain your solution.
0
votes
1answer
31 views

A question on combinatorics

Bob and Laura have bought an apartment, and are going to carpet the floor in the kitchen. The kitchen has size $2 \times n$, where $n$ is a positive integer. In how many ways can Bob and Laura ...
0
votes
1answer
25 views

Recurrence to find P(n). P(n) is the number of ways to decorate a strip of size n with tiles.

There are three kind of tile. One is of size 1. Second is of size 2 of green color. Third is of size 2 with blue color. These are the values I found but I can not figure out the formula. P1 1 p2 3 p3 ...
0
votes
1answer
46 views

Recursive Formula

I have found a question in my book and I have solve it, but I am not sure about the answer. The question goes like this: Find a recursive formula that will give the number of ways to order $N$ ice ...
1
vote
1answer
56 views

Need help with proving the recursion

Let $p_{k}(n)$ indicate the number of partitions of n into k parts. Prove: $$p_{k}(n) = p_{k-1}(n-1) + p_{k}(n-k)$$ Example: There are two partitions of $5$ into three parts. $5 = 3+1+1$ $5 = ...
2
votes
1answer
66 views

Solve a recursion using generating functions?

Given the recursive equation : $$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$ A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get : $$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$ ...
2
votes
1answer
91 views

Identity involving a recursive product

Here is yet another problem related to plane partitions. Given the recursive formula $$ \begin{align*} F(0)&=1,\\ F(r)&=\prod_{i=1}^r\frac{i+2r-1}{2i+r-2}F(r-1). \end{align*} $$ How can we ...
1
vote
1answer
56 views

Combinatorial Recursion 2

Define a recursion $a(n,k)$ that gives the number of ways to choose $n$ items out of $k$ types of items, with the condition that we must choose $2, 4$, or $6$ items of each type. So $2p+4q+6r = n$ ...
0
votes
1answer
73 views

Combinatorial Recursion

Define a recursion that gives the number of sequences that include the numbers $0,1,2,3$ with an even number of $1$'s and an even number of $0$'s. So far I got $$a(n) = 2a(n-1) + 2a(n-2)$$ which ...
3
votes
1answer
108 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} ...
1
vote
2answers
81 views

Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills ...
1
vote
2answers
38 views

Simple linear recursion

$x_n=\frac{x_{n-1}}{a}+\frac{b}{a}$ with $a>1, b>0$ and $x_0>0$ I tried to solve it using the generating function but it does not work because of $\frac{b}{a}$, so may you have an idea.
2
votes
1answer
92 views

OEIS A000255 recursion.

I encountered the sequence A000255. $a(n)$ counts permutations of $[1,...,n+1]$ having no substring $[k,k+1]$ I am finding difficulty in proving it. Can you please give any clues or hints on how to ...
2
votes
3answers
224 views

Need to find the recurrence equation for coloring a 1 by n chessboard

So the question asks me to find the number of ways H[n] to color a 1 by n chessboard with 3 colors - red, blue and white such that the number of red squares is even and number of blue squares is at ...
7
votes
1answer
504 views

Bell numbers, recursions, bijections

The $n$th Bell number, named after Eric Temple Bell (although he was far from the first to think about them), is the number of partitions of a set of cardinality $n$. If they are written in the top ...