In strong Induction for the induction hypothesis you assume for all K, p(k) for k
If for example I am working with trees and not natural numbers can I still use this style of proof?
For example if I want my induction hypothesis to be that p(k) for k < n where n is a node in the tree and everything smaller than/bellow it (The nodes children,k) is assumed to be true.
In the proof would I have to define what the < operator does for two nodes?
On
Yes, strong induction will work on a partially ordered set such as a tree, as long as there are no infinite downward chains $a_1 > a_2 > a_3 > \ldots$.
On
Sure you can. As André Nicolas says, this is called structural induction, and it applies to data types that are inductively defined, that is, the structure, or rather, the construction of their elements is given (a) by some base cases, and (b) by some step cases involving already given elements.
Binary trees for example are given (a) by one base case, the tree consisting of one leaf node (no children), and (b) one step case declaring that if you have already constructed two binary trees then you can join their roots to a common root node (parent node) and obtain a new binary tree.
In order to show that every binary tree has some property using induction, you would have to follow the construction cases: (a) show that the one-node tree has the property; (b) assume that two already constructed trees have the property (this would be the induction hypothesis), and show that the new tree that you get by joining them via a common root node must also have the property. You can also do the "strong" (also called course-of-values) version (b'): assume that the two already constructed trees, as well as their own subtrees have the property, and then show that the new tree must also have it.
A conceptual subtlety here is that you perform the induction not on the nodes of the tree, but on the different possible ways these can be pieced together to form the tree (that is to say: on the structure of the tree); the different types of nodes, namely leaf nodes and root nodes, are just your induction pivots. To this point, notice that structural induction generalizes the usual induction on natural numbers: just think of the data type of unary trees labelled by the characters $0$, $S$, and defined by (a) $0$ is a unary tree, and (b) if $m$ is an already constructed unary tree, then $Sm$ is also a unary tree. Here, the zero symbol $0$ plays the role of the one-node base case, and the successor symbol $S$ the (joining) root node of the step case. Indeed, when we perform the usual induction we induct not on nodes (which could only mean node labels) $0$ and $S$, but on numbers $0$, $1$, $2$, ..., that is on "unary trees" $0$, $S0$, $SS0$, ..., where $0$ for zero and $S$ for the successor $+1$ serve as the induction pivots.
In the proof would I have to define what the < operator does for two nodes?
Well, the symbol "<" in this case would refer to the subtree relation, right?: $t<s$ would mean $t$ is a (proper) subtree of $s$. This has to be defined before you prove anything using it — in this case, you would want to use it if you performed strong induction. Note that definitions in inductively defined data types are wont to be recursive, to follow the inductive pattern as well: (a) define what the subtrees of the one-node tree are; (b) given the subtrees of two already constructed trees, define what the subtrees of the new tree are.
Induction, and strong induction, are used to prove statements that are indexed by the natural numbers $\mathbb{N}=\{1,2,3,\ldots\}$. $k$ and $n$ need to be natural numbers, with a minimum value ($0$ or $1$ are the usual choices). The statements need not be natural numbers, for example, the first statement $p(1)$ could be that "node number 1 satisfies property x" and the second statement $p(2)$ could be that "nodes number 1 and 2 satisfy property x" etc.