You can't induct for this problem because induction will only show a property for all finite strings. Arbitrary-length finite strings, but still finite.