We can draw any alkane from ethane upwards like this:
...../P'
C-C-Q'
.....\R'
where the Cs are carbon atoms, and P', Q' and R' are collections of carbon atoms (possibly empty) such that P = C-P', Q = C-Q' and R = C-R' are alkanes. Let P, Q and R be p-,q- and r-alkanes respectively. Then p+q+r = n+1, where n is the number of carbon atoms in the whole thing. The way I've done things p,q and r could be 1,2,3,4,5...., but given n we must have p between 1 and n-1, q between 1 and n-p and r = n+1-p-q.
Two porblems arise with trying to do an induction on this basis. Firstly we don't care about the order of p,q and r, but that's easily fixed; more seriously, given an alkane, the choice of start atom (the C on the left of the diagram) is arbitrary, aside from the insistence that it only connects to one other carbon atom (such an atom must exist for ethane or bigger, as alkanes have no cycles), and the same alkane could have representations which look different from each other by choosing a different start atom. Can anyone think of a better representation that deals with this second issue?