A 2x2 room is easily filled as, once the empty square is allocated, the mere remainder of the room makes up a single tile. As you can see from this picture, an empty square can also fit into any 4x4 pattern and it is that top-leftmost 4x4 pattern (herein referred to as the TL pattern) that is key for filling any size room.

In this example, the empty square has a coordinate of (2,5) in an 8x8 room. Once the first 4x4 pattern was found, the TL pattern from the previous image was wrapped around it and the pink tile filled in what was left. Another way of looking at the process (I'm unsure as to which is more efficient for an algorithm) is the pink tile being placed on the corner of the 4x4 pattern (this corner is also the center of the room; in larger rooms this corner is at the center of a subsection of the room), followed by the TL pattern wrapping around the pink tile.

The following process illustrates how to fill a 32x32 room with an empty tile coordinate of (2,19):

Divide the room into fourths and find which fourth the empty square occupies...

Divide that fourth into fourths and find which of those fourths (a sixteenth of the whole room) the empty square occupies...

Repeat that process, finding the empty square's position in a fourth of that sixteenth (a sixty-fourth of the whole room)...

Finally, find the empty square in a fourth of the sixty-fourth (a two hundred fifty-sixth of the whole room).

The reasoning behind finding the empty square's position relative to fourths is that the room is filled via an inverse process. You might find it more streamlined to simply find the empty square in a two hundred fifty-sixth from the start, but the room is still filled by fourths:

You take the empty square and generate a 4x4 pattern around it. This can be done similar to the 8x8 example above. The remainder of the two hundred fifty-sixth that the empty square occupies becomes a tile, then you wrap a 2x2 pattern around that with empty spaces becoming a tile (or have a tile attach itself to the corner of the two hundred fifty-sixth [which corner is determined by being in the center of a sixty-fourth] with other tiles generating around that tile).

From there, you repeat whichever process you use to generate an 8x8 square, followed by a 16x16 square, until you fill the whole 32x32 room.

This process can be used to fill any sized room presented in your problem, but unfortunately I am not so mathematically minded as to translate this process into an algorithm.

(P.S. All of the images in this post were created using MS Paint, so you can take your Photoshop and shove it. )

OK. I misread the original post, so my proof has to be adapted.

The statement is that we can tile any 2^n x 2^n room leaving only a designated square empty.

We proceed by induction, as before. The designated square is in one of the four 2^(n-1) x 2^(n-1) squares, and we know we can tile that square leaving any 1x1 square we want empty because of the induction hypothesis. For the other three 2^(n-1) x 2^(n-1) squares, tile them leaving the 1x1 square at the middle of the room empty, and then add a tile in the middle covering the three empty spots thus created.

Again, this is easy to implement as a recursive function.

Sorry about the confusion.

The way recursion works, you write a function that performs the total task or any of the smaller tasks in which it can be decomposed.

The first thing to figure out is what parameters the function should take (i.e., what describes one of the tasks). In this case, a tasks is "tile the 2^n x 2^n square whose top-left corner is at top_row and left_column and which leaves empty the square at empty_row and empty_column". So you need to pass parameters n, top_row, left_column, empty_row and empty_column.

The next thing to figure out is when the process stops, which is usually the first thing the function will check. You can do something like "if n is 0, there's nothing to do".

You then figure out how to decompose the task you are given into smaller subtasks, and call the function recursively with each subtask.

Give that a try.