I did get a thrill when it dawned on me that because we proved the base case, all the rest of them fall like dominoes once we prove (k+1)^2 = k^2 + (2k+1). The beauty of induction wasn't lost on me, but the beauty of the k^2 thing, I admit, is. Maybe I actually haven't "got it".

I had a moment of awe and joy when I visually was able to recognize Newton's proof of a limit in principia. I'd like that recreated.

We hypothesize that
n(n+1)/2 = 1 + 2 + 3 + ... + (n-1) + n
We see that it is true when n=1
So we assume it's true for a random K. That is:
K(K+1)/2=1+2+3+...+(K-1)+(K)

We prove it is true for the (K+1) case
if our assumption is true, it should be the case that:
(K+1)((K+1)+1)/2=1+2+3+...+(K-1)+K+(K+1)

Since 1+2+3+...+(K-1)+K = K(K+1)/2
then
(K+1)((K+1)+1)/2 = K(K+1)/2 + (K+1)

after multiplying by two to find common denominator then manipulating we get

(K+1)((K+1)+1)/2 = K((K+1)+1)/2

Boom!

The bold is what you're trying to prove, but don't state it and then rearrange it. Proceed directly to that result in a linear proof so you don't feel like you're doing it backwards or going in circles. Just say:

1 + 2 + 3 + ... + k + k+1 = k(k+1)/2 + k+1

Factoring out k+1:

= (k+1)(k/2 + 1)

= (k+1) (k+2)/2

= (k+1)(k+1+1)/2.

That makes sense.

That's important because otherwise you actually are technically asserting the consequent. You stated what you wanted to prove, and rearranged it to get a true result. In general that doesn't mean that what you started with has to be true. It is in this case because the steps are reversible, but you have to actually show the steps in the right order. That's why you thought it wasn't really proven, and failed to get the proper thrill. It also causes you trouble with algebra in other problems.

Try proving that the sum of the first n cubes is [n(n+1)/2)]^2.

Remember, write the equation you want to prove, A = B, but then show that A leads to B, not just that A = B leads to something true. Only work with 1 side of the equation, and make it look like the other side.

Show that [n(n+1)/2]^2 is the sum of the first n cubes

Base case obviously true
Assume that it's true for some arbitrary k case that
[k(k+1)/2]^2=1^3 + 2^3 + ... + (k-1)^3 + k^3

Prove for k+1 that
[(k+1)((k+1)+1)/2]^2 = 1^3 + 2^3 + ... + (k-1)^3 + k^3 + (k+1)^3
[(k+1)((k+1)+1)/2]^2 = [k(k+1)/2]^2 + (k+1)^3
[(k+1)((k+1)+1)/2]^2 = (k^2(k+1)^2 + 4(k+1)^3)/4
[(k+1)((k+1)+1)/2]^2 = (k+1)^2 * (k^2 + 4k + 1)/4
[(k+1)((k+1)+1)/2]^2 = (k+1)^2 * (k+2)^2/4
[(k+1)((k+1)+1)/2]^2 = [(k+1)(k+2)/2]^2
[(k+1)((k+1)+1)/2]^2 = [(k+1)((k+1)+1)/2]^2

That was algebraically much harder.

I was actually trying to prove that before you posted it, but I couldn't figure out how to make a general expression that would give me the terms. Any tips for that process in general?

The right side is exactly right, but you don't need the left side. That's not part of the proof. You just write that down once for your own purposes so you know what you're trying to get. That algebra was straightforward. You can see that you need a (k+1)^2, and you can factor one out, so you do it. Then you recognize a square. These were the same 2 steps used in the previous 2 problems combined in 1 problem, so it was a good choice by me. Was it a thrill?


That's mathematics. These can be tough, but there's a whole list of those formulas here.

Anyone here know z-transforms??

Exams in two weeks, sitting at home with fever, can´t go to school and the literature sucks...

Can´t get a part of problem im working on right. To go forward i have to find the inverse z-transform of:

H(Z) = (1 - z^-1) / (1 - z^-1 + 0.5*z^-2)


First step should be factorizing the denominator.
I get the poles to be (1/sqrt(2))*e^(±i * pi/4))

But how do i go from here to do the inverse transform and get h(n) ??

It was a little exciting, yeah. Like I said before though, it was a little "meh" because the hard part would have been coming up with the formula first, which I didn't do. But, nonetheless, it was good stuff.

If you think that's more exciting, try to come up with a formula from the sum of the fourth powers (or seventh powers if you wish).

Okay, but what is it about the fifth and sixth powers that would make you omit them?

Six is not a prime power. With five, it's more of a personal thing.

Got it. As far as techniques go: we are trying to turn a series into a general equation; when I've seen the formula for the sum of the first n integers derived it was done so by writing the series in ascending order and then writing it in descending order, then adding them together and dividing both sides of our equation by two. Is it generally advisable to proceed that way?

No.

You can use induction to prove that patterns you notice are true in general, or to disprove them also. For example, it's easy to notice that

1^3 + 2^3 = 9 = 3^2 = (1 + 2)^2

1^3 + 2^3 + 3^3 = 36 = 6^2 = (1 + 2 + 3)^2

1^3 + 2^3 + 3^3 + 4^3 = 100 = 10^2 = (1 + 2 + 3 + 4)^2

You might like to see if this works in general, and if so, to prove it. You already saw that's true by deriving the formulas for these by induction. For the integers it was n(n+1)/2, and for the cubes it was [n(n+1)/2]^2. Getting n(n+1)/2 was easy by the trick of writing the sum backwards and forwards. You can also do it by computing half the area of an n by (n+1) row of boxes using the trick shown here. The above then suggests that the sum of the cubes is the square of this or [n(n+1)/2]^2. You then show this by induction which you have done. You also could show that the above is true by induction directly instead proving [n(n+1)/2]^2. That's a good exercise that you could benefit from. Show that the sum of the first n cubes is the square of the sum of the first n positive integers. That's a remarkable and unexpected result, and one that you can now notice and derive on your own. You will need to do some algebra using series. You will need the fact that the sum of the first n positive integers is n(n+1)/2.

You could also notice that the formula for the sum of the first n positive integers is a quadratic in n, and the sum of the first n cubes is a 4th order polynomial in n. You might speculate that the sum of the first n powers of p is a polynomial that is of (p+1) order in n. That would mean the sum of the powers of 2 would be 3rd order. The general form would be

1^2 + 2^2 + 3^2 + ... = an^3 + bn^2 + cn + d.

Then you could find a,b,c, and d by writing 4 equations in 4 unknowns by plugging in 4 values of n that work.

a*1^3 + b*1^2 + c*1 + d = 1^2 = 1

a*2^3 + b*2^2 + c*2 + d = 1^2 + 2^2 = 5

a*3^3 + b*3^2 + c*3 + d = 1^2 + 2^2 + 3^2 = 14

a*4^3 + b*4^2 + c*4 + d = 1^2 + 2^2 + 3^2 + 4^2 = 30

Then solve for a,b,c, and d. You get a=1/3, b = 1/6, c=1/2, and d=0, so your theoretical formula is that the sum of the first n squares is

1/3*n^3 + 1/2*n^2 + 1/6*n

or in factored form

n(n+1)(2n+1)/6.

In theory, you could derive the sums for any power this way.

Haven't read that post yet Bruce. Going to though.

Trying to approximate the sum of a series correct to four decimal places using the alternating series estimation theorem. |R_ n|=|S-S_n|<=R_(n+1)

so lets say I find that the b_6 term is -.000036

I'm correct in thinking that this term alters S_5 in such a way that the first 4 decimal places of the sum will remain unchanged, right? This seems pretty straightforward to me. So then we would say that S_5 is correct up to 4 decimal places.

Looking at the solution manual for confirmation gives me a sense that I have some fundamental misunderstanding of what it means for a number to be correct to 4 decimal places because consistently they are picking a b_n such that it is always 1 greater than mine. It isn't a matter of calculating my b_n wrong either because the manual confirms (in it's listing of the terms for the partial sum) that my b_n is what I think it is.

You need to do a partial fraction expansion. Letting the roots be r1 and r2,

(1 - z^-1) / [(z^-1 - r1)(z^-1 - r2)] = A / (z^-1 - r1) + B / (z^-1 - r2)

Now use the Heaviside coverup method to evaluate A and B. If you multiply through by (z^-1 - r1) you get

(1 - z^-1) / (z^-1 - r2) = A + B(z^-1 - r1) / (z^-1 - r2).

Then evaluate at z^-1 = r1 so the B term goes away, and you're left with

A = (1 - r1) / (r1 - r2).

Then multiply though by (z^-1 - r2) and evaluate at z^-1 = r2 to get rid of the A term and get B.

(1 - z^-1) / (z^-1 - r1) = A(z^-1 - r2) / (z^-1 - r1) + B

B = (1 - r2) / (r2 - r1).

Then the inverse transform of

H(z) = A / (z^-1 - r1) + B / ( z^-1 - r2) =

-A/r1 / (1 - 1/r1 * z^-1) - B/r2 / (1 - 1/r2 * z^-1)

when the region of convergence (ROC) is |z| > 1/r1 and |z| > 1/r2 is the causal impulse response

h[n] = -A/r1 * (1/r1)^n * u(n) - B/r1 * (1/r2)^n * u(n)

and when the ROC is |z| < r1 and |z| < 1/r2 you get the anti-causal impulse response

h[n] = A/r1 * (1/r1)^-n * u(-n-1) - B/r1 * (1/r2)^-n * u(-n-1).

Then there are 2 other possibilities for the ROC when
|z| > 1/r1, |z| < 1/r2 and |z| < 1/r1, |z| > 1/r2
where you would mix and match the appropriate terms from the above transforms accordingly. You should have been given a ROC with the z-transform, or been asked for the causal or anti-causal solutions. Normally we want the causal solution.

Figured it out. Ignore this.

You can't ever know you have enough terms to be correct to any number of decimal places only looking at how much the sum changed. Suppose the sum after 4 terms was 1.444499999999. Now how much does it need to change before the 4th decimal place changes from a 4 to a 5? Only 0.000000000001. You would need the sum itself. Perhaps it's off by 1 because they want you to look at the sum. If you can only look at how much it changed, then you can only make it accurate to within say 0.00005 which is different from making the 4th decimal point correct. In that case since its alternating, the actual sum must be between the last 2 values of the sum you computed, so it can't be off by more than the amount it changed from S_6 to S6 which is |b_6|. What is the series and your answer and their answer?

The series was Σ (-1)^(n-1)*n^2/10^n (from n=1 to infinity)

I have that b_6= -.000036
so I assumed that S_5's first four decimals would remain unchanged. This is generally mistaken, for reasons you mention above, but in this case
s_5 = .06765 and
s_5+b_6 =.06761

so that s_5 is correct to within 4 decimal places.

They have that
b_7=.000005
s_6=.067614
s_6+b_7=.067619


similarly for Σ(-.8)^n/n! (n=1 to infinity)
I have that
b_7=-.000042
s_6=-.550633
s_6+b_7= -.550675 (correct to within four decimal places)

they have that
b_8=.000004
s_7=-.550675
s_7+b_8=-.550671

They're just going by the fact that |b_6| < 0.0001, but |b_5| = 0.00025 > 0.00001, so you need to go with S_6, not S_5. S_6 changed by |b_6| from S_5, so it is within 0.0001, but S_5 changed by |b5| from S_4, so it could be off by more than 0.0001 if you didn't know what it was. In this case the 4th digit of S_5 is correct, but it wouldn't be if you rounded it.

>n = 1:10
> n
[1] 1 2 3 4 5 6 7 8 9 10
> b = (-1)^(n-1)*n^2/10^n
> s = cumsum(b)
> b
[1] 0.100000000 -0.040000000 0.009000000 -0.001600000 0.000250000
[6] -0.000036000 0.000004900 -0.000000640 0.000000081 -0.000000010
> s
[1] 0.100000 0.060000 0.069000 0.067400 0.067650 0.067614 0.067619 0.067618
[9] 0.067618 0.067618


In this case |b_7| < 0.0001, but |b_6| = 0.000364 > 0.0001, so you go with S_7, not S_6. Did they go with S_8? I don't know why. Even S_6 is correct in the 4th decimal place, but not if you round the correct answer.

> b = (-.8)^n/factorial(n)
> s = cumsum(b)
> b
[1] -0.800000000000 0.320000000000 -0.085333333333 0.017066666667
[5] -0.002730666667 0.000364088889 -0.000041610159 0.000004161016
[9] -0.000000369868 0.000000029589
> s
[1] -0.80000 -0.48000 -0.56533 -0.54827 -0.55100 -0.55063 -0.55067 -0.55067
[9] -0.55067 -0.55067

Also I find these theorems (eg error bounds on alternating series) easier to remember if you know WHY they are true, rather than just THAT they are true. Especially with error for alternating series, it's a very simple explanation.

I've been thinking about it a bit and I can't figure it out. Why would the absolute value of the difference between the nth partial and the actual sum be less than the next number in the series?

Because the actual sum is always between the last 2 partial sums that you compute. That's due to the fact that the terms alternate sign, and they keep getting smaller in magnitude. So you effectively add a positive number, then subtract a smaller positive number so you stay higher than the first value, then add a smaller positive number so you stay lower than the second value, then subtract a smaller positive number so you stay higher than the third value, etc. The positive terms you add overshoot the actual value that we're converging to, and the positive terms you subtract undershoot it, so you are making successive over and under estimates. You know that S_6 can't be off by any more than |b_6| because the actual sum that we're converging to has to be between S_5 and S_6, so it can't be any farther from S_6 than S_5, and S_5 is |b_6| away from S_6 since S_5 + b_6 = S_6. That's why if you need to be closer than 0.0001, and |b_6| is the first one that does that, then you go with S_6 = S_5 + b_6, not S_5 as you were doing.

Here, picture worth a thousand words. This is the sum of (-1)^(n) * 1/n. Note how the limit ln(2) (red line) is always between the values of the partial sum, so the error is always less than the amount that was added which is |b_n|. Don't be afraid to graph this stuff to help you understand what's going on.