Prediction and Motion Estimation As far as I understand, the motion estimation is a process, where when we have two frames t and t+1 we search for the blocks/pixels that changed position and then encode that change with a motion vector. So in the end we have only the frame t and its encoded successor.

After that we use compensation in order to use these motion vectors, and further encode only the difference between the "vectorized" frame t+1 and the frame t.

Firstly, am I right? Secondly, when the prediction issue comes into play? I'm reading about prediction all the time, but in the sequence I've described, I don't see any prediction happening anywhere.
The prediction comes in when actually adding the motion estimation to both frames t and t+1.  Consider a video of a ninja cutting a melon in half, but shot at a very short shutter speed, so as to freeze motion in each frame.  The motion estimator notices that the sword is moving between frame t and frame t+1.  (It also moved between frame t-1 and t, and also frame t+1 to t+2).  Frame t gets half the motion from t-1 to t and half the motion from t to t+1.  The latter half is the prediction.  Frame t+1 gets half the motion from t to t+1 and half the motion from t+1 to t+2.  In this way, the video does not appear to shift half a frame later than the audio.