Recursive Subchessboards

Posted by Kenon on Aug. 26, 2010, 3:44 p.m.

I used that terminology and method to describe a proof of 1+2+3+…+n=n(n+1)/2

How? Its easyHELLA DIFFICULT to explain. Imagine you have a chessboard of (n+1)x(n+1) dimensions. We will go about proving two things here: The sum of the squares below the diagonal is equal to the 1+2+3+…+n part, and that that is equal to n(n+1)/2

Part 1: Lets go ahead and define the (n+1)x(n+1) as Chessboard C. Assuming on the value of n, C can have multiple square subchessboards inside of the main area, compromising areas such as 1x1 or 2x2. Indeed, each cell on the chessboard is a subchessboard. Onto the proof, for Chessboard C, there are rows R such that 1<=R<=n+1. We also must define the total amount of cells on the bottom layer on any row of a chessboard that are below the diagonal. Since exactly 1 and only 1 square is occupied by the diagonal on the bottom row of any chessboard (when caring about only one diagonal), We can define it as for any chessboard of RxR size, there exist R-1 squares on the base row below the diagonal. Recursively, if we assume there are RxR subchessboards inside of Chessboard C, then we can calculate the value of the cells as being (1-1)+(2-1)+(3-1)+(4-1)+…+(n+1-1), or equivalently, 0+1+2+3+…+n, accounting for all the cases of the RxR subchessboards that align that the base encompasses the entirety of the squares below the diagonal for said row R of chessboard C.

Part 2: Assume same situation, Chessboard C. The base of chessboard C (and likewise the height) are equal to (n+1)x(n+1). Assume a triangle cutting through the squares below the diagonal such a right triangle of base and height n and n respectively divide the squares below the diagonal into 1 region A and a total of n regions I will call B, respectively. Each of these regions in B is a right triangle of length and height 1 and 1 respectively. The total sum of the number of squares below the diagonal on C will be equal to the area of Region A + the combined area of regions B. A=n(n)/2=(1/2)n^2. B=(1/2)(1)(1)=1/2. There are a total of n copies of region B, so the sum will be (1/2)(n^2)+1/2(n)=(n^2+n)/2=n(n+1)/2

Part 3: We proved that the top part was the total sum of squares below the diagonal via recursive subchessboards. We proved that the bottom formula with geometric formulas. They are equal. So 1+2+3+…+n=n(n+1)/2

I know that I probably wrote it wrong (but the math is all right) but if you got the idea, say something about it.

Comments

mazimadu 14 years, 4 months ago

I remember this formula. I used it in primary school to calculate 1+2+3+….+99+100=5050

sirxemic 14 years, 4 months ago

You are doing it the hard way.

0+1+2…+(n-2)+(n-1)+n=(0+n)+(1+(n-1))+(2+(n-2))+…=n+n+n+…

That happens (n+1)/2 times when starting at 0 and n is uneven.

When n is even you simply start at 1, where (n+1) happens n/2 times.

Done.

Not very formal but yeah.

Juju 14 years, 4 months ago

You're sorta there Xemic. The proof is best explained by this website.

Josea 14 years, 4 months ago

I'm perfectly happy with the mathematical induction we all know and love :)

Base case - Assume it holds for n - Prove it holds for n+1

Juju 14 years, 4 months ago

Induction is the shit.

sirxemic 14 years, 4 months ago

Oh I gotta agree with Josea, actually.

<3 Induction

Kenon 14 years, 4 months ago

Yeah I know but I had to prove it via an (n+1)x(n+1) chessboard.

F1ak3r 14 years, 4 months ago

I third the <3 for induction.

sirxemic 14 years, 4 months ago

Quote:
Yeah I know but I had to prove it via an (n+1)x(n+1) chessboard.
Well that's silly :3