Tagged Questions
8
votes
1answer
149 views
Function mapping challange
For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant
mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$
and $f(k) = f(f(k + 1))$.
This is ...
0
votes
1answer
22 views
Sum of series with generic term inside it
I have the following series:
$$
\sum_{k=0}^{+\infty} k \cdot a^k \cdot s_k
$$
Having $|a| < 1$ and where $s_k \in [0,1]$ is a generic sequence having the property for which $\lim_{k \to ...
1
vote
1answer
50 views
Triangle tiling proof
How to prove that the number of triangles in the tiling below can be found by the formula
$$\left\lfloor\frac{n(n+2)(2n+1)}8\right\rfloor\;,$$
where $n$ is the number of vertical layers? (For the ...
3
votes
1answer
41 views
Finding a Linear Recurrence Relation
A model for the number of lobsters caught per year is
based on the assumption that the number of lobsters
caught in a year is the average of the number caught in
the two previous years.
...
0
votes
1answer
17 views
Probability of ordered sequence
There are 3 squares, 5 triangles, and 4 circles.
I need to generate possibilities of certain sequences if they are randomly generated.
What is the probability that all the squares are grouped, next ...
2
votes
3answers
41 views
Proof for two sequences producing the maximum value when sorted
I am trying to improve my discrete Math skills by doing some proof exercises. But I am struggling to understand how to start proving the following hypothesis:
$$
S = {x}_1{y}_1 + {x}_2{y}_2 + \ldots ...
0
votes
1answer
39 views
Help with understanding a summation formula
I am having trouble understanding the derivation of the summation formula below.
$$\sum_{k=1}^N \dfrac1{(k+1)(k+2)} = \dfrac{N}{2N+4}$$
0
votes
3answers
66 views
A sequence is defined by: $a(1) = 1$ and $a(n + 1) = 3a(n) - 1$ for $n \ge 1$. What is $a(100)$?
A sequence is defined by: $a(1) = 1$ and $a(n + 1) = 3a(n) - 1$ for $n \ge 1$. What is $a(100)$?
Solution. The first few terms of $a(n)$ are $1,2,5,14,\ldots$. The general solution to the ...
0
votes
2answers
64 views
Give a recursive definition with initial condition…how did they get the answer?
The function $f (n) = 5n + 2, n = 1, 2, 3, \ldots $
Im sure its a simple problem, but im really confused...how did they get the answer ? could someone explain
$f (n) = f (n - 1) + 5, f (1) = 7$
...
0
votes
0answers
32 views
How to formulize this logarithmic expression?
If you have this list of numbers {$1, 2, 4, 7, 11, 16, 21, 27, 33, ...$}
Where the list starts at 1, then the next number is $1 + x + \left\lceil\log_2{x}\right\rceil$ where $x$ is the current ...
1
vote
3answers
63 views
Formulating a formula for$ P_n$
The sequence is $P_2=\dfrac 34, P_3=\dfrac 23, P_4=\dfrac 58, P_5=\dfrac 35, P_6=\dfrac 7{12}, P_7=\dfrac 47$.
I'm having trouble putting this formula for $P_n$ on paper.
2
votes
3answers
107 views
Prove that $\sum_{k=0}^n \binom{n}{k} k^2 = n(n+1) 2^{n-2}$ [duplicate]
$$\sum_{k=0}^n \binom{n}{k} k^2 = n(n+1) 2^{n-2}$$
2
votes
1answer
46 views
Are linear shift register sequences corresponding to reciprocal polynomials equivalent?
I am looking into sequences generated by LFSRs (linear shift register sequences). I was wondering if sequences corresponding to reciprocal connection polynomials (that is, corresponding to shift ...
0
votes
0answers
75 views
Discrete m-sequence problem
I'm having trouble with the following question, any help appreciated.
If {$a_n$} with $(n \geq 0)$ is an m-sequence in $Z_p$ of period $p^{k}-1$, $p$ is prime and $k \geq 1$.
And we let $r$, a ...
7
votes
1answer
120 views
Equation $\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2$
I think this equality is very inters
prove that:
$\displaystyle\sum_{k=0}^{n-1}(-1)^{n-k-1}\dfrac{(n+k)!}{(k!)^2(n-k-1)!}=n^2$
0
votes
1answer
89 views
Compute infinite sum
I need to compute $$f(x)=\sum_{i=0}^\infty \left(\left\lfloor\frac{i}{2^x}\right\rfloor+x+1\right)(1-p)^{i-1}p$$and minimize it with respect to $x$ (an expression which will depend on $p$).
1
vote
0answers
37 views
Matrix Representation of Integer Series
I would like some feedback regarding this process or the meaning of
this process.
Let say that I have a discrete time series:
S = [1 2 3 4 5]
And that I represent this serie by a stochastic matrix M ...
4
votes
4answers
162 views
Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$
How can I calculate the following sum involving binomial terms:
$$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$
Where the value of n can get very big (thus calculating the binomial ...
1
vote
2answers
201 views
How do I simplify nested summations? Also how does it work? Like a loop?
$$
\sum^{n}_{j=1}\sum^{n}_{k=1} jk
$$
How do I simplify this? Also can someone explain how this works?
its gonna be like this right? or am I misunderstanding it?
$$
\sum^{n}_{j=1}(j+2j+3j+...+nj)
$$
0
votes
2answers
48 views
Why doesn't this formula work in summation of cubes? but works in summation of squares
$$
\sum^{n}_{k=1} k^3 = ({n^2(n+1)^2})/4
$$
right?
say for example k not equal to 1, why doesn't this work? I subtracted the summation of k-1?
$$
\sum^{n}_{k!=1} k^3 = ({n^2(n+1)^2 - (k-1)^2k^2})/4
...
1
vote
0answers
51 views
The Continuity of the Discrete Time Fourier Transform of Absolutely Summable Series
I saw on a book to follwoing claim:
Given an Absolutely Summable Series $ \sum_{n = -\infty }^{\infty}\left | x\left [ n \right ] \right | \leqslant \infty $, Namely, $ l_1 $ series it is possible to ...
3
votes
0answers
158 views
Closed-form expression for sum of Vandermonde matrix elements
Given the Vandermonde matrix:
$$\begin{pmatrix}1^0 & 1^1 & 1^2 & ... & 1^n \\
2^0 & 2^1 & 2^2 & ... & 2^n \\
\vdots & \vdots & \vdots & \ddots & ...
1
vote
0answers
119 views
Can this series be expressed in closed form, and if so, what is it?
Can this series be expressed in closed form, and if so, what is it?
$$
\sum_{n=1}^\infty\frac{1}{9^{n+1}-1}
$$
1
vote
2answers
194 views
Computing Double Summation with Kronecker Delta
I am having difficulty proving that
\begin{align}
\sum_{i = 0}^{M-1} \sum_{j = 0}^{N - 1} \delta \left[a - \left(Ni + j\right)\right] = 1
\end{align}
for $M < N$ and $0 \leq a < NM$. Where ...
1
vote
1answer
34 views
How to approximate a complex linear homogenous recurrence with constant coefficients with a simple one?
Is there some standard way to approximate a complex linear homogenous recurrence with constant coefficients with a simple one?
For example, I might want to approximate
$$
...
2
votes
2answers
80 views
Proving that a sequence is decreasing
How could I prove the following statement without using induction? I've been staring at this for the better part of an hour. (To be fair, I'm not very good at proof writing) Thanks in advance!
Define ...
0
votes
1answer
77 views
Sum $\sum_{k=0}^n p(k) \cdot f(k)$ in terms of $f(n)$ and $\sum_{k=0}^n f(k)$
I am aware of that this question shall be rather basic, and that there may be a lot of resources on this, but it is quite complicated to use Google to find relevant results for this (I have not found ...
4
votes
1answer
148 views
Two sums with Fibonacci numbers
Find closed form formula for sum: $\displaystyle\sum_{n=0}^{+\infty}\sum_{k=0}^{n} \frac{F_{2k}F_{n-k}}{10^n}$
Find closed form formula for sum: $\displaystyle\sum_{k=0}^{n}\frac{F_k}{2^k}$ ...
0
votes
0answers
19 views
Efficient way to batch calculate a function over _k-cuttings_?
You are given a function $f : \mathbb{Z} \rightarrow \mathbb{Z}$
Call a k-cutting of a positive integer $x$, a k-tuple of nonnegative integers $(a_1, a_2, ... , a_n)$ such that $\sum{a_i} = x$
For ...
1
vote
0answers
60 views
Count Exclusive Partitionings of Points in Circle, Closing Double Recurrence?
I am studying a problem that I have worked out is equivalent to the following:
Problem Description
Given N distinct points on the border of a circle, there are $B_N$ ways to partition them - where ...
4
votes
1answer
151 views
Efficiently evaluating the Motzkin numbers
So I made an error on the question here: $T_N = 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k}$
The correct formula I'm trying to solve is more complicated and as follows:
$$T_0 = T_1 = 1 $$
$$T_{N+1} = T_N + ...
3
votes
1answer
57 views
A closed form for $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$?
I've narrowed down a problem I am working on to the following recurrence:
$$\begin{align*}
T_0 &= T_1 = 1\\
T_N &= 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k}
\end{align*}$$
I'm stuck on how to close ...
4
votes
2answers
180 views
Evaluating complicated sum
Evaluate for a fixed $m\neq 1$ ( $m\in \mathbb{N}$ )
$$\sum _{k=1}^{n}\left[\left( \sum _{i=1}^{k}i^{2}\right) \left(\sum _{k_{1}+k_{2}+...+k_{m}=k}\dfrac {\left( k_{1}+k_{2}+\ldots +k_{m}\right) ...
0
votes
2answers
112 views
Z-Transform Identity
I've come across an identity and would like to know if it has some sort of formal name or derivation or explanation or something! Also, I'm curious as to whether others are aware of such an identity.
...
1
vote
2answers
532 views
Finite sum of reciprocal odd integers
Mathematica tells me that $\sum\limits_{i=1}^n \frac1{2i-1}$ is equal to $\frac12 H_{n-1/2}+\log\,2$, where $H_n$ is a harmonic number.
Why is this true? Is there a general strategy for solving sums ...
1
vote
1answer
233 views
Discrete Laplace Tranform.
Yesterday ago I was reading how the Laplace Transform can be interpreted as the continuous analog of the discrete functional dependance of the power series $$f(x) = \sum a(n) x^n$$
This is to say, ...
2
votes
3answers
195 views
What is the expression for this summation?
Known that $\sum_{n=0}^{\infty}{x^n}{z^n}=\frac{1}{1-xz}$. If we have $\sum_{n=0}^{\infty}\frac{{x^n}{z^n}}{n\beta + \alpha}$ where $\beta, \alpha $ are element of real numbers but not equal $0$. ...
2
votes
1answer
405 views
Method for variable substitution in multiple summation
I asked this question on mathoverflow, someone suggested me to ask
here as well. So I post it here. Thanks for helping.
I want to ask: is there any general method for variable substitution in ...
1
vote
1answer
117 views
$(a_{1}+ a_{2} + …+a_{k})^{n}$ where $k >2$, what does it generate?
Binomial expansion generates the Pascal triangle but what does it generate when you have different amount of terms there?
You can see here the geometric generation with only 2 terms. I am interested ...
22
votes
15answers
3k views
Proof that $\sum\limits_{k=1}^nk^2 = \frac{n(n+1)(2n+1)}{6}$?
I am just starting into calculus and I have a question about the following statement I encountered while learning about definite integrals:
$$\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$$
I really ...
14
votes
4answers
254 views
Solve recursion $a_{n}=ba_{n-1}+cd^{n-1}$
Let $b,c,d\in\mathbb{R}$ be constants with $b\neq d$. Let
$$\begin{eqnarray}
a_{n} &=& ba_{n-1}+cd^{n-1}
\end{eqnarray}$$
be a sequence for $n \geq 1$ with $a_{0}=0$. I want to find a closed ...
10
votes
2answers
310 views
Summation by parts of $\sum_{k=0}^{n}k^{2}2^{k}$
I want to evaluate this sum
$$\sum_{k=0}^{n}k^{2}2^{k}$$ by summation by parts (two times) and I need to know, if my approach was right.
I know the formula for summation by parts is $$\sum u\Delta ...
5
votes
3answers
134 views
Looking for a function $f$ such that $f(i)=2(f(i-1)+f(\lceil i/2\rceil))$
I'm looking for a solution $f$ to the difference equation $$f(i)=2(f(i-1)+f(\lceil i/2\rceil))$$ with $f(2)=4$. Very grateful for any ideas.
PS. I've tried plotting the the initial values into ...
2
votes
0answers
50 views
Relating product integrals to indefinite products
The product integral is the multiplicative version of standard integrals. Indefinite products are the discrete counterpart to this integral; they multiply iterations on a function $f(x)$ by each ...
3
votes
2answers
135 views
Write the following sequence as a recurrence relation
Write the following sequence as a recurrence relation (with sufficient initial values specified):
$$b_n=1-\frac{1}{2^n} \forall n\in\mathbb{N}^*$$
I think I am suppose to use induction (e.g. n-1) to ...
3
votes
1answer
156 views
Proof whether or not 1/k by 1/(k+1) rectangles fit inside a unit square
I am reading Concrete Mathematics and came across an interesting problem, number 37 of chapter 2. The answers to exercises lists no known answer to this problem:
Will all the 1/k by 1/(k+1) ...
1
vote
2answers
126 views
is this expression O(n^2) or O(n^3)?
$$\sum_{i=0}^{n-1} (i+1)(n-1)$$
Is that $O(n^2)$ or $O(n^3)$? Can you explain me how you found it? Thanks.
3
votes
8answers
409 views
How to compute the formula $\sum \limits_{r=1}^d r \cdot 2^r$?
Given $$1\cdot 2^1 + 2\cdot 2^2 + 3\cdot 2^3 + 4\cdot 2^4 + \cdots + d \cdot 2^d = \sum_{r=1}^d r \cdot 2^r,$$
how can we infer to the following solution? $$2 (d-1) \cdot 2^d + 2. $$
Thank you
2
votes
1answer
273 views
Proof of closed form Hofstadter G-Sequence
I'm working through a discrete maths text book and was stumped as to how to prove the closed form solution of the Hofstadter G-Sequence
$a(0) = 0$ and $a(n) = n - a(a(n-1)), n \geq 1$
The closed ...
