Sorthon

So im in graph theory at my college and i have never done a single proof in my life. Normally the teacher gives us an option of either a proof or a program sense this class is also required for math majors. This time around however he decided to give every one one proof and one program and as far as the proof goes i am 100% lost. The question goes as follows: Corollary 3.2.24: Every binary tree of height h has at most 2^(k+1)-1 vertices. Prove corollary 3.2.24 directly with the "strong form" of induction using its weaker induction: For some h>0 and all k<=h-1, a binary tree of height k has at most 2^(k+1)-1 vertices. I'm not looking for a direct answer but any help to point me in the right direction would be much appreciated. I know that a binary tree with 2 vertices will have a hieght of 1, then plugging in 1 into 2^(1+1)-1 which will = 3 stating that a tree with height 1 will have at most three vertices sense a vertex may only have two children in a binary tree. The tree will look like this: 0 / \ 0 0 The height of this tree is still only one and the largest amount of possible vertices with out increasing the height is 3.

i actually have Lovelace on my list of subjects to add. Like i said before the issue im having is lack of usable sources

I appreciate The ideas, what i have talked about so far is the abacus, Stonehenge, how computers where originally people who did calculations for a living who were usually women) i have mentioned Alan Turing but have not actually talked about him yet but i will get there, and i talk a good bit about John Backus and how his development of FORTRAN revolutionized programming while also explaining what a programming language is in laymen terms and discussing what caused him to want to make a high level language in the first place. things on the list to be included are Alan Turing, Difference engines, and Bletchley Park to provide an example of how computer science isn't only used for computer programs to play games and work out of the house. At the moment I'm adding in information about Bletchley Park and i have the book codebreakers but i am having a hard time finding out how exactly they did what they did so that i can partain it too computer science. I know they used a large machine to figure out the code and what not, I have the wiki page open but i need to find it in the book sigh... My main issue that im fighting with is that i can not use wikipedia as a source. I already have planned to talk about the Difference engine, and will also touch on the Turing machine.

Well I have already talked about the abacus and Stonehenge so really as far back as I can. I am trying to stay away from the very recent stuff just because frankly I don't find it fun because most recent stuff isn't really new ideas its just new ways of using old ideas. I am trying to focus more on the roots rather then the leaves.

So I took on the task of writing a paper about the history behind modern computer science and computing. My question to you all is what kind of fun facts or knowledge can you all share that i may add in my paper. I really want to have some cool info because I'm trying to make the paper appeal to those who don't really know much about computer science. If at all possible can you share what sources your getting your information from and if its just your prior knowledge then i will just site you , in which case some kind of name that i could use to site would be helpful.