Question

Completely lost on a recurring relation problem.

Answer 1

When \(k=1\) you have: \[
\frac{1+2+\ldots +n}{n^2} = \frac{n(n+1)}{2n^2} = \frac{n+1}{2n} = \frac 12 + \frac 1n
\]

Answer 2

The limit will go to \(1/2\).

Answer 3

Much simpler than I was expecting. Thank you.

Answer 4

I haven't tried actually proving it though.

Answer 5

I don't think it should bee too hard to show : \[
1^k+2^k+3^k+\ldots +n^k\leq cn^k
\]

Answer 6

Subtract \(n^k\) from both sides and you get: \[
1^k+2^k+\ldots + (n-1)^k\leq (c-1)n^k = c'n^k
\]

Answer 7

I'm using a bit of circular logic here, aren't I?

Answer 8

Hmm, perhaps I'm wrong, let's rethink this...

Answer 9

\[
1^k+2^k+\ldots +n^k \leq n^k+n^k+\ldots + n^k = nn^k = n^{k+1}
\]

Answer 10

were are using \(0<i\leq n \implies i^k\leq n^k\) for that fist step.

Answer 11

The best way to write it is:\[
1\leq i\leq n \implies i^k\leq n^k \implies \sum_{i=1}^ni^k \leq \sum_{i=1}^n n^k = nn^k= n^{k+1}
\]

Answer 12

You're the best. Would you care to help me on another one real quick?

What is the general form of the solutions of a linear homogeneous recurrence
relation if its characteristic equation has the roots −1, −1, −1,2,2,5,5,7?

Answer 13

What is a linear homogenous recurrence relations. You need to explain that first.

Answer 14

Example: \[a_{n} = 2a _{n-1} + 4a _{n-2}\] Correct?

Answer 15

Not sure, but if you think so I'd take your word for it. That would basically mean: \[
T(n) = 2T(n-1)+4T(n-2)
\]

Answer 16

But what would the characteristic equation be?

Answer 17

Just double checked, and I'm correct.

So, the characteristic equation would be:

\[r ^{2} - 2r -4\]

Answer 18

=0

Answer 19

shouldn't the degree be equal to the number of roots?

Answer 20

I'm honestly not sure.