I need to proof by induction that at full binary tree there are $\frac{n+1}{2}$ leafs if $|V|=n$.
So, I won't write you the whole proof, just my idea, and I'd like to know if this OK...
So we assume the at full binary tree there is $\frac{n+1}{2}$ leafs for a specific $n$.
We have to prove that the assume is correct for tree with $k=n+2$ vertices.
How we proving it?
We will take a tree with $n$ vertices, we know that the induction assumption is good for this tree.
Then we will take one leaf and add him 2 vertices.
So, we have a tree with $\frac{n+2-1}{2}$ leafs (because, we add 2 leafs so there is $n+2$ vertices, and we lose 1 leaf because wee add to him two children, but we get 2 leafs).
And then we get what we want to prove...
I'm right? If not - Where is my mistake?
Thank you!
You have a mistake. If you are proving by induction on $n$, your induction hypothesis is that all trees of size $n$ have $\frac{n+1}{2}$ leaves and you must prove from this hypothesis that all trees of size $n+2$ have $\frac{(n+2)+1}{2}$ leaves. The step that you're missing is showing that all trees of size $n+2$ are extensions of trees of size $n$ - otherwise there might be some rogue tree of size $n+2$ that your argument never addressed.
If on the other hand you want to prove that if a given tree with $n$ vertices has $\frac{n+1}{2}$ leaves then a tree extending that tree with $n+2$ vertices has $\frac{(n+2)+1}{2}$ nodes, you are using a form of induction called structural induction. I am not sure whether you are allowed to use this technique.